论文标题
具有有界分层的树宽和有限度的图形的聚类着色
Clustered Coloring of Graphs with Bounded Layered Treewidth and Bounded Degree
论文作者
论文摘要
图形着色的聚类是单色组件的最大尺寸。本文在图形类别中使用有界的分层树宽的图表研究着色，其中包括平面图，有界的Euler属的图形，图形可嵌入在固定表面上，每个边缘的交叉数，地图图，以及其他示例。我们的主要定理说，每个带有分层树宽的图最多$ k $，最高$δ$的最高度为$ 3 $ - 可油，聚类$ o（k^{19}δ^{37}）$。这是群集上的第一个已知的多项式结合。对于有界属的图表的埃斯佩尔和码头的相应结果，这大大改善了。
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 layered treewidth, 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.
