论文标题
沉浸和聚集着色
Immersion and clustered coloring
论文作者
论文摘要
Hadwiger和Hajós推测，对于每个正整数$ t $，$ k_ {t+1} $ - 次要免费图形和$ k_ {t+1} $ - 拓扑次要的次要免费图形分别适当地$ t $ - 颜色 - 可油。已经对这两个猜想的群集着色版本进行了广泛的研究，仅需要单色组件才能具有界限。在本文中，我们考虑了Hadwiger's和Hajós的沉浸式变化的集体着色版，由Lescure和Meyniel提出，并由Abu-Khzam和Langston独立。我们确定$ h $ immersion无图形的最小颜色数量，对于任何固定的图形$ h $，最多可达一个小的添加剂绝对常数。对于无限的许多图$ h $，我们的结果很紧。 本文开发的关键机械是一种引理，将图表上的聚类着色问题降低到其树状分解或树状分解的躯干上的簇。该机械的副产品是Alon，Ding，Oporowski和Vertigan结果的统一证明，也是作者和OUM的结果，涉及次要家族中有界最大程度的群集着色图。
Hadwiger and Hajós conjectured that for every positive integer $t$, $K_{t+1}$-minor free graphs and $K_{t+1}$-topological minor free graphs are properly $t$-colorable, respectively. Clustered coloring version of these two conjectures which only require monochromatic components to have bounded size has been extensively studied. In this paper we consider the clustered coloring version of the immersion-variant of Hadwiger's and Hajós' conjecture proposed by Lescure and Meyniel and independently by Abu-Khzam and Langston. We determine the minimum number of required colors for $H$-immersion free graphs, for any fixed graph $H$, up to a small additive absolute constant. Our result is tight for infinitely many graphs $H$. A key machinery developed in this paper is a lemma that reduces a clustering coloring problem on graphs to the one on the torsos of their tree-cut decomposition or tree-decomposition. A byproduct of this machinery is a unified proof of a result of Alon, Ding, Oporowski and Vertigan and a result of the author and Oum about clustered coloring graphs of bounded maximum degree in minor-closed families.
