Improper Colourings inspired by Hadwiger's Conjecture

Abstract

Hadwiger's Conjecture asserts that every $K_t$-minor-free graph has a proper $(t-1)$-colouring. We relax the conclusion in Hadwiger's Conjecture via improper colourings. We prove that every $K_t$-minor-free graph is $(2t-2)$-colourable with monochromatic components of order at most $\lceil \frac{1}{2}(t-2)\rceil$. This result has no more colours and much smaller monochromatic components than all previous results in this direction. We then prove that every $K_t$-minor-free graph is $(t-1)$-colourable with monochromatic degree at most $t-2$. This is the best known degree bound for such a result. Both these theorems are based on a decomposition method of independent interest. We give analogous results for $K_{s,t}$-minor-free graphs, which lead to improved bounds on generalised colouring numbers for these classes. Finally, we prove that graphs containing no $K_t$-immersion are $2$-colourable with bounded monochromatic degree.

References in corpus (7)

• A relative of Hadwiger's conjecture
• Defective colouring of graphs excluding a subgraph or minor
• Coloring planar graphs with three colors and no large monochromatic components
• Islands in minor-closed classes. I. Bounded treewidth and separators
• Partitioning $H$-minor free graphs into three subgraphs with no large components
• Islands in graphs on surfaces
• Improper coloring of graphs with no odd clique minor

Cited by in corpus (18)

• Planar graphs have bounded queue-number
• Clustered 3-Colouring Graphs of Bounded Degree
• Clustered Colouring in Minor-Closed Classes
• Defective and Clustered Choosability of Sparse Graphs
• Clustered Graph Coloring and Layered Treewidth
• Clustered Variants of Hajós' Conjecture
• Clustered Coloring of Graphs Excluding a Subgraph and a Minor
• Improper coloring of graphs with no odd clique minor
• On coloring numbers of graph powers
• Improved bounds for weak coloring numbers
• Separating layered treewidth and row treewidth
• Immersion and clustered coloring
• Clustered Coloring of Graphs with Bounded Layered Treewidth and Bounded Degree
• Colouring Strong Products
• Bad News for Chordal Partitions
• Universality in minor-closed graph classes
• Boxicity, poset dimension, and excluded minors
• The grid-minor theorem revisited