Clustered colouring of graphs excluding a fixed minor: the Norin–Scott–Seymour–Wood conjecture $\chi_\star(\mathcal{M}_H)\le 2\,\overline{td}(H)-2$

For a fixed graph $H$, let $\mathcal{M}_H$ be the class of graphs with no $H$-minor. The clustered chromatic number $\chi_\star(\mathcal{M}_H)$ is the least number of colours needed to colour every graph in $\mathcal{M}_H$ so that each monochromatic component has bounded size (the bound may depend on $H$). Norin, Scott, Seymour and Wood proved that $\chi_\star(\mathcal{M}_H)$ is tied to the connected tree-depth $\overline{td}(H)$ of $H$ and conjectured the sharp bound $\chi_\star(\mathcal{M}_H)\le 2\,\overline{td}(H)-2$; they constructed graphs $H_k$ with $\chi_\star(\mathcal{M}_{H_k})\ge 2k-2=2\,\overline{td}(H_k)-2$, so the constant 2 is best possible if the conjecture holds. The conjecture is known for $\overline{td}(H)\le 3$, for classes of bounded tree-depth or bounded path-width, for planar $H$ (Liu, via bounded tree-width), and for cliques and complete bipartite graphs (Dujmović–Esperet–Morin–Wood, resolving the clustered Hadwiger conjecture). The best bound for arbitrary $H$ is $\chi_\star(\mathcal{M}_H)\le 3\,\overline{td}(H)-3$ (Liu). The problem is to prove or disprove the conjecture in the remaining cases, namely general nonplanar forbidden minors.

Background

A graph $H$ is a minor of a graph $G$ if $H$ can be obtained from a subgraph of $G$ by contracting edges. Hadwiger's conjecture asserts that every graph with no $K_t$-minor is properly $(t-1)$-colourable; it is one of the deepest open problems in graph theory, which motivated the study of relaxed colourings of minor-closed classes. In a $k$-colouring of $G$, each colour class induces a subgraph whose connected components are called monochromatic components. The colouring has clustering $N$ if every monochromatic component has at most $N$ vertices, and defect $d$ if every monochromatic component has maximum degree at most $d$. For a graph class $\mathcal{F}$, the clustered chromatic number $\chi_\star(\mathcal{F})$ is the minimum $k$ such that for some integer $N$ every graph in $\mathcal{F}$ has a $k$-colouring with clustering $N$; the defective chromatic number $\chi_\Delta(\mathcal{F})$ is defined analogously with bounded defect. Since a colouring with clustering $N$ has defect $N-1$, $\chi_\Delta(\mathcal{F})\le\chi_\star(\mathcal{F})$. These parameters can be much smaller than the chromatic number: Edwards, Kang, Kim, Oum and Seymour proved that every $K_{t+1}$-minor-free graph is $t$-colourable with bounded defect, a verbatim defective analogue of Hadwiger's conjecture. For general forbidden minors the correct analogue of a clique is the closure of a rooted tree. The closure of a rooted tree $T$ is the graph on $V(T)$ in which two vertices are adjacent exactly when one is an ancestor of the other, and the height of $T$ is the maximum number of vertices on a root-to-leaf path. The tree-depth $td(G)$ is the minimum height of a rooted forest whose closure contains $G$ as a subgraph, and the connected tree-depth $\overline{td}(G)$ is the minimum height of a single rooted tree whose closure contains $G$; the two coincide for connected graphs but can differ for disconnected ones, since the parts of $G$ may have to be stacked inside one tree. Writing $\mathrm{CT}_{h,k}$ for the closure of the balanced $k$-ary tree of height $h$, a simple induction shows that $\mathrm{CT}_{h,k}$ has no $(h-1)$-colouring with clustering $k$; since $\overline{td}(\mathrm{CT}_{h,k})=h$ and, for every $H$, the graphs $\mathrm{CT}_{\overline{td}(H),\ell}$ with $\ell\ge|V(H)|$ contain $H$ while every minor of $\mathrm{CT}_{\overline{td}(H)-1,k}$ has connected tree-depth at most $\overline{td}(H)-1$, one gets the lower bound $\overline{td}(H)-1\le\chi_\Delta(\mathcal{M}_H)\le\chi_\star(\mathcal{M}_H)$. Ossona de Mendez, Oum and Wood conjectured that $\chi_\Delta(\mathcal{M}_H)=\overline{td}(H)-1$ for every $H$, proving the case $\overline{td}(H)\le 3$; this defective conjecture was confirmed in full by Chun-Hung Liu. Norin, Scott, Seymour and Wood then initiated the clustered theory: they proved $\chi_\star(\mathcal{M}_H)\le 2^{\overline{td}(H)+1}-4$ (so $\chi_\star(\mathcal{M}_H)$ is tied to $\overline{td}(H)$), proved the case $\overline{td}(H)\le 3$, constructed graphs $H_k$ with $\overline{td}(H_k)=k$ and $\chi_\star(\mathcal{M}_{H_k})\ge 2k-2$ (showing clustered colouring genuinely needs more colours than defective colouring), and posed the conjecture. Subsequent work established the conjecture for minor-closed classes of bounded tree-depth (where $\chi_\star(\mathcal{M}_H)=\overline{td}(H)-1$ exactly) and of bounded path-width (Norin–Scott–Wood), and for planar $H$, equivalently classes $\mathcal{M}_H$ of bounded tree-width (the tree-width of a graph is the minimum size of a largest bag in a tree-decomposition of the graph, where a tree-decomposition assigns a vertex set, called a bag, to each node of a tree so that every edge is covered by some bag and the bags containing any fixed vertex form a connected subtree; by the excluded-grid theorem of Robertson and Seymour, $\mathcal{M}_H$ has bounded tree-width exactly when $H$ is planar), where Liu's results give $\chi_\star(\mathcal{M}_H)\le 2\,\overline{td}(H)-2$. Dujmović, Esperet, Morin and Wood resolved the clustered Hadwiger conjecture: every $K_t$-minor-free graph is $(t-1)$-colourable with bounded clustering, and every $K_{s,t}$-minor-free graph is $(s+1)$-colourable with bounded clustering, settling the clique and complete-bipartite cases of the conjecture with room to spare. Combining Liu's defective theorem with the Liu–Oum theorem that every $H$-minor-free graph partitions into three induced subgraphs with components of bounded (degree-dependent) size yields the best known general bound $\chi_\star(\mathcal{M}_H)\le 3\,\overline{td}(H)-3$. Whether the factor 3 can be improved to the conjectured 2 is open precisely for nonplanar forbidden minors.

Problem Statement

Prove or disprove the conjecture of Norin, Scott, Seymour and Wood (their Conjecture 4; Conjecture 1.7 in Liu's 'Defective coloring is perfect for minors'): for every graph $H$, if $\mathcal{M}_H$ denotes the class of graphs with no $H$-minor and $\overline{td}(H)$ denotes the connected tree-depth of $H$ (the minimum height of a rooted tree whose closure contains $H$ as a subgraph), then

$$\chi_\star(\mathcal{M}_H)\le 2\,\overline{td}(H)-2.$$

Equivalently: for every graph $H$ there exists an integer $N(H)$ such that every $H$-minor-free graph has a $(2\,\overline{td}(H)-2)$-colouring in which every monochromatic component has at most $N(H)$ vertices. The conjecture is already known for $\overline{td}(H)\le 3$, for classes of bounded tree-depth or bounded path-width, for planar $H$, and for cliques and complete bipartite graphs; the open instances are the remaining nonplanar forbidden minors, where the best known bound is $\chi_\star(\mathcal{M}_H)\le 3\,\overline{td}(H)-3$. A proof must establish the bound for every graph $H$ (including disconnected and nonplanar $H$); a refutation must establish the existence of a graph $H$ such that for every integer $N$ some $H$-minor-free graph admits no $(2\,\overline{td}(H)-2)$-colouring with clustering $N$. Note that the bound, if true, is best possible: Norin–Scott–Seymour–Wood constructed graphs $H_k$ with $\overline{td}(H_k)=k$ and $\chi_\star(\mathcal{M}_{H_k})\ge 2k-2$, so no smaller constant can replace the factor 2 in general.

References

1. Sergey Norin, Alex Scott, Paul Seymour, David R. Wood. Clustered Colouring in Minor-Closed Classes. Combinatorica 39 (2019), 1387–1412. doi:10.1007/s00493-019-3848-z, arXiv:1708.02370, https://arxiv.org/abs/1708.02370 (origin of the conjecture, their Conjecture 4; Theorem 3 gives the tightness examples)
2. Chun-Hung Liu. Defective coloring is perfect for minors. Combinatorica 44 (2024), 467–507. doi:10.1007/s00493-024-00081-8, arXiv:2208.10729, https://arxiv.org/abs/2208.10729 (restates the conjecture as his Conjecture 1.7; proves the defective conjecture and the linear and planar-case bounds)
3. Sergey Norin, Alex Scott, David R. Wood. Clustered colouring of graph classes with bounded treedepth or pathwidth. Combinatorics, Probability and Computing 32 (2023), 122–133. doi:10.1017/S0963548322000165, arXiv:2012.05554, https://arxiv.org/abs/2012.05554
4. Patrice Ossona de Mendez, Sang-il Oum, David R. Wood. Defective colouring of graphs excluding a subgraph or minor. Combinatorica 39 (2019), 377–410. doi:10.1007/s00493-018-3733-1, arXiv:1611.09060, https://arxiv.org/abs/1611.09060 (source of the defective conjecture $\chi_\Delta(\mathcal{M}_H)=\overline{td}(H)-1$ and its $\overline{td}\le 3$ case)
5. Vida Dujmović, Louis Esperet, Pat Morin, David R. Wood. Proof of the Clustered Hadwiger Conjecture. arXiv:2306.06224 (2023), https://arxiv.org/abs/2306.06224 (resolves the clique and complete-bipartite cases)
6. Chun-Hung Liu, Sang-il Oum. Partitioning $H$-minor free graphs into three subgraphs with no large components. Journal of Combinatorial Theory, Series B 128 (2018), 114–133. doi:10.1016/j.jctb.2017.08.003, arXiv:1503.08371, https://arxiv.org/abs/1503.08371 (the defect-to-clustering factor-3 conversion behind the best general bound)
7. Robert Hickingbotham, Dong Yeap Kang, Sang-il Oum, Raphael Steiner, David R. Wood. Clustered Colouring of Odd-$H$-Minor-Free Graphs. arXiv:2308.15721 (2023, revised 2024), https://arxiv.org/abs/2308.15721 (adjacent odd-minor analogue)
8. Katherine Edwards, Dong Yeap Kang, Jaehoon Kim, Sang-il Oum, Paul Seymour. A Relative of Hadwiger's Conjecture. SIAM Journal on Discrete Mathematics 29 (2015), 2385–2388. doi:10.1137/141002177, https://doi.org/10.1137/141002177 (defective Hadwiger analogue; source of the clustered Hadwiger problem later resolved by Dujmović et al.)