Clustered coloring of graphs with bounded layered treewidth and bounded degree
Clustered coloring of graphs with bounded layered treewidth and bounded degree
复制标题
具有有界分层树宽和有界度的图的聚类着色
DOI：
10.1016/j.ejc.2023.103730
复制
发表时间：
2023
影响因子：
1
通讯作者：
Wood, David R.
中科院分区：
文献类型：
--
作者：
Liu, Chun-Hung;Wood, David R.
图着色的聚类是单色分量的最大大小。本文研究了有界分层树宽的图类中的有界聚类着色问题，这些图类包括平面图、有界Euler亏格图、可嵌入固定曲面且每条边有界交叉数的图、地图图等.我们的主要定理是，每个分层树宽不超过k，最大度不超过Δ的图都是3-可着色的，聚类时间为O（k 19 Δ 37）。这是第一个已知的多项式约束的聚类。这大大改进了Esperet和Jaret关于有界亏格图的一个相应结果。
The clustering of a graph coloring is the maximum size of monochromatic components. This paper studies colorings with bounded clustering in graph classes with bounded layeredtreewidth, which include planar graphs, graphs of bounded Euler genus, graphs embeddable on a fixed surface with a bounded number of crossings per edge, map graphs, amongst other examples. Our main theorem says that every graph with layered treewidth at most k and with maximum degree at most Δ is 3-colorable with clustering O (k 19 Δ 37). This is the first known polynomial bound on the clustering. This greatly improves upon a corresponding result of Esperet and Joret for graphs of bounded genus.
登录
查看更多内容
影响因子：
1.4
作者：
KRATOCHVIL, J
通讯作者：
KRATOCHVIL, J
DOI：
10.1145/509907.509910
发表时间：
2002-05
期刊：
--
影响因子：
--
作者：
M. Schaefer;E. Sedgwick;Daniel Stefankovic
通讯作者：
M. Schaefer;E. Sedgwick;Daniel Stefankovic
DOI：
--
发表时间：
2016
期刊：
影响因子：
--
作者：
B. Mohar;B. Reed;D. Wood
通讯作者：
D. Wood
平面图和地图中 (k, r) 中心的固定参数算法
DOI：
--
发表时间：
2005
期刊：
TALG
影响因子：
--
作者：
E. Demaine;F. Fomin;M. Hajiaghayi;D. Thilikos
通讯作者：
D. Thilikos
不断发展的数据库的存储管理
DOI：
--
发表时间：
1997
期刊：
Proceedings 38th Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
J. Kleinberg;R. Motwani;P. Raghavan;Suresh Venkatasubramanian
通讯作者：
Suresh Venkatasubramanian