Immersion and clustered coloring

Abstract

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.

References in corpus (12)

• Layered Separators in Minor-Closed Graph Classes with Applications
• Improper Colourings inspired by Hadwiger's Conjecture
• A relative of Hadwiger's conjecture
• Breaking the degeneracy barrier for coloring graphs with no $K_t$ minor
• Islands in minor-closed classes. I. Bounded treewidth and separators
• Partitioning $H$-minor free graphs into three subgraphs with no large components
• Clustered Graph Coloring and Layered Treewidth
• Clustered Variants of Hajós' Conjecture
• An even better Density Increment Theorem and its application to Hadwiger's Conjecture
• Clustered Coloring of Graphs Excluding a Subgraph and a Minor
• Halfway to Hadwiger's Conjecture
• A global decomposition theorem for excluding immersions in graphs with no edge-cut of order three

Cited by in corpus (3)

• Clustered Coloring of Graphs with Bounded Layered Treewidth and Bounded Degree
• Biclique immersions in graphs with independence number 2
• A global decomposition theorem for excluding immersions in graphs with no edge-cut of order three