Clustered Colouring in Minor-Closed Classes

Abstract

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 prove that for every graph $H$, the clustered chromatic number of the class of $H$-minor-free graphs is tied to the tree-depth of $H$. In particular, if $H$ is connected with tree-depth $t$ then every $H$-minor-free graph is $(2^{t+1}-4)$-colourable with monochromatic components of size at most $c(H)$. This provides the first evidence for a conjecture of Ossona de Mendez, Oum and Wood (2016) about defective colouring of $H$-minor-free graphs. If $t=3$ then we prove that 4 colours suffice, which is best possible. We also determine those minor-closed graph classes with clustered chromatic number 2. Finally, we develop a conjecture for the clustered chromatic number of an arbitrary minor-closed class.

References in corpus (4)

• Improper Colourings inspired by Hadwiger's Conjecture
• A relative of Hadwiger's conjecture
• Defective colouring of graphs excluding a subgraph or minor
• Partitioning $H$-minor free graphs into three subgraphs with no large components

Cited by in corpus (7)

• Clustered 3-Colouring Graphs of Bounded Degree
• Clustered Variants of Hajós' Conjecture
• Clustered Coloring of Graphs with Bounded Layered Treewidth and Bounded Degree
• Colouring Strong Products
• Defective coloring is perfect for minors
• The Excluded Tree Minor Theorem Revisited
• The grid-minor theorem revisited