论文标题
簇的3色图
Clustered 3-Colouring Graphs of Bounded Degree
论文作者
论文摘要
如果每个单色组件最多都具有$ c $顶点，则图（不一定是正确的）顶点着色具有“群集” $ c $。我们证明，具有最高度$δ$的平面图可与聚类$ o（δ^2）$ 3色。以前的最佳界限是$ O（δ^{37}）$。平面图的这一结果将可以在有界的欧拉属表面上绘制的图表概括，每个边缘数量有界数。然后，我们证明，排除固定小调的最高度$δ$的图形可与clustering $ o（δ^5）$相三色。此结果的最佳先前界限为$δ$。
A (not necessarily proper) vertex colouring of a graph has "clustering" $c$ if every monochromatic component has at most $c$ vertices. We prove that planar graphs with maximum degree $Δ$ are 3-colourable with clustering $O(Δ^2)$. The previous best bound was $O(Δ^{37})$. This result for planar graphs generalises to graphs that can be drawn on a surface of bounded Euler genus with a bounded number of crossings per edge. We then prove that graphs with maximum degree $Δ$ that exclude a fixed minor are 3-colourable with clustering $O(Δ^5)$. The best previous bound for this result was exponential in $Δ$.
