Clustered chromatic number via treedepth bound
Conjecture 4 · arXiv:1708.02370
Status partial high confidence
Conjecture 4 from arXiv:1708.02370 — that $\chi^*(\mathcal{M}_H) \leq 2\,\mathrm{td}(H) - 2$ for every graph $H$ — has been proved for the special cases of minor-closed classes with bounded treedepth and bounded pathwidth by Norin, Scott, and Wood (arXiv:2012.05554, 2022), with the pathwidth bound shown to be best possible. The general statement remains open. The internal reference arXiv:2508.14332 is a false match and concerns the unrelated weak coarse Menger conjecture.
Cited literature (1)
-
Proves Conjecture 4 for minor-closed classes with bounded treedepth (Theorem 1, exact value $\chi^\star(\mathcal{G}) = \mathrm{tcn}(\mathcal{G}) - 1$) and bounded pathwidth (Theorem 2, best-possible bound), while the general conjecture remains open.
Reviewer notes. Conjecture 4 is proved for bounded-treedepth and bounded-pathwidth minor-closed classes (arXiv:2012.05554, 2022); the general case chi*(M_H) <= 2*td(H) - 2 remains open. Third internal reference (arXiv:2508.14332) is a false match unrelated to this conjecture.
Context
Theorem 3 establishes the matching lower bound $\chi^*(\mathcal{M}_{H_k}) \geq 2k-2$ for graphs $H_k$ with $\mathrm{td}(H_k) = k$, showing that defective and clustered chromatic numbers can differ. The authors conjecture this lower bound is tight, and note the conjecture is proved in Section 4 for the special case $\mathrm{td}(H) = 3$.
Notes. PDF source — math notation partially garbled; statement reconstructed from context. Introduced with the phrase 'We conjecture an analogous upper bound'.
Source paper
Clustered Colouring in Minor-Closed Classes
Sergey Norin, Alex Scott, Paul Seymour, David R. Wood · 2018-07-29
https://arxiv.org/abs/1708.02370
PDF source