...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>SIAM Journal on Discrete Mathematics >ISLANDS IN GRAPHS ON SURFACES
【24h】

ISLANDS IN GRAPHS ON SURFACES

机译：表面上的岛屿

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

An island in a graph is a set X of vertices such that each element of X has few neighbors outside X. In this paper, we prove several bounds on the size of islands in large graphs embeddable on fixed surfaces. As direct consequences of our results, we obtain the following: (1) Every graph of genus g can be colored from lists of size 5, in such a way that each monochromatic component has size O(g). Moreover, all but O(g) vertices lie in monochromatic components of size at most 3. (2) Every triangle-free graph of genus g can be colored from lists of size 3, in such a way that each monochromatic component has size O(g). Moreover, all but O(g) vertices lie in monochromatic components of size at most 10. (3) Every graph of girth at least 6 and genus g can be colored from lists of size 2, in such a way that each monochromatic component has size O(g). Moreover, all but O(g) vertices lie in monochromatic components of size at most 16. While (2) is optimal up to the size of the components, we conjecture that the size of the lists can be decreased to 4 in (1), and the girth can be decreased to 5 in (3). We also study the complexity of minimizing the size of monochromatic components in 2-colorings of planar graphs.
机译：图中的一个岛是一组顶点X，因此X的每个元素在X之外几乎没有邻居。在本文中，我们证明了可嵌入固定表面的大型图中的岛的大小有几个边界。作为我们结果的直接结果，我们获得以下信息：（1）属g的每个图都可以从大小为5的列表中着色，以使每个单色分量的大小为O（g）。此外，除O（g）以外的所有顶点都位于大小最大为3的单色分量中。（2）每个属g的无三角形图都可以从大小为3的列表中着色，使得每个单色分量的大小为O。 （G）。此外，除O（g）以外的所有顶点都位于大小最大为10的单色分量中。（3）每个围长图至少为6和属g可以从大小为2的列表中着色，以使每个单色分量具有尺寸O（g）。此外，除O（g）顶点外，所有顶点均位于大小最大为16的单色分量中。虽然（2）在分量的大小之前是最佳的，但我们推测列表的大小可以减小为（1）中的4。 ，并且可以将围长减小到（3）中的5。我们还研究了在平面图的2种颜色中最小化单色分量大小的复杂性。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号