论文标题
图形类别的聚集着界面的特性或路径。
Clustered colouring of graph classes with bounded treedepth or pathwidth
论文作者
论文摘要
一类图形的“群集色号”是最小整数$ k $，因此，对于某些整数$ c $，同类中的每个图是$ k $ - 颜色的，最多具有$ c $的单色组件。我们确定具有有界TreeDepth的任何次要类别的群集的色数，并证明了在任何带有有界路径的次要闭合类的群集的色数上最好的上限。结果，我们确定了每个次要封闭类的分数群集的色数。
The "clustered chromatic number" of a class of graphs is the minimum integer $k$ such that for some integer $c$ every graph in the class is $k$-colourable with monochromatic components of size at most $c$. We determine the clustered chromatic number of any minor-closed class with bounded treedepth, and prove a best possible upper bound on the clustered chromatic number of any minor-closed class with bounded pathwidth. As a consequence, we determine the fractional clustered chromatic number of every minor-closed class.
