Immersion and clustered coloring

DOI10.1016/J.JCTB.2022.07.010MaRDI QIDQ2099417zbMATH OpenOpenAlexFDO

Authors Chun-Hung Liu

Publication date 23 November 2022

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2007.00259

zbMATH Keywords

clustered coloringgraph immersion

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Combinatorial probability (60C05)

Abstract: Hadwiger and Haj'{o}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'{o}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.

Recommendations

• Coloring immersion-free graphs
• Clustered variants of Hajós' conjecture
• Clustered colouring in minor-closed classes
• Improper colourings inspired by Hadwiger's conjecture
• List-coloring graphs without subdivisions and without immersions

Cites work

• A global decomposition theorem for excluding immersions in graphs with no edge-cut of order three
• A minimum degree condition forcing complete graph immersion
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
• A relative of Hadwiger's conjecture
• A relaxed Hadwiger's conjecture for list colorings
• An extremal function for contractions of graphs
• Bounded size components -- partitions and transversals.
• Breaking the degeneracy barrier for coloring graphs with no K_t minor
• Clustered variants of Hajós' conjecture
• Complete graph immersions and minimum degree
• Contractibility and the Hadwiger conjecture
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Graph coloring and the immersion order
• Graph Theory and Probability
• Hadwiger's conjecture for \(K_ 6\)-free graphs
• Hajos' graph-coloring conjecture: Variations and counterexamples
• scientific article; zbMATH DE number 3865318 (Why is no real title available?)
• scientific article; zbMATH DE number 4104981 (Why is no real title available?)
• scientific article; zbMATH DE number 3243267 (Why is no real title available?)
• scientific article; zbMATH DE number 3102312 (Why is no real title available?)
• Immersing small complete graphs
• Improper colourings inspired by Hadwiger's conjecture
• Layered separators in minor-closed graph classes with applications
• Lower bound of the Hadwiger number of graphs by their average degree
• On the conjecture of Hajos
• Partitioning \(H\)-minor free graphs into three subgraphs with no large components
• Partitioning into graphs with only small components
• The four-colour theorem
• The structure of k-chromatic graphs

Cited in

(8)

• Clustered colouring in minor-closed classes
• A global decomposition theorem for excluding immersions in graphs with no edge-cut of order three
• Coloring immersion-free graphs
• List-coloring graphs without subdivisions and without immersions
• Clustered coloring of graphs with bounded layered treewidth and bounded degree
• Biclique immersions in graphs with independence number 2
• A note on clique immersion of strong product graphs
• Biclique immersions in graphs with independence number 2 (extended abstract)

This page was built for publication: Immersion and clustered coloring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2099417)