Clustered chromatic number for odd-H-minor-free graphs

Conjecture 2 · arXiv:2308.15721

arXiv Conjecture high confidence— first stated 2024-10-18

Authors: Robert Hickingbotham, Dong Yeap Kang, Sang-il Oum, Raphael Steiner, David R. Wood

Status open high confidence

Conjecture 2 of arXiv:2308.15721 asserts that for every graph $H$, both the defective chromatic number $\chi_{\Delta}(\mathcal{G}_H^{\text{odd}})$ and the clustered chromatic number $\chi_{\star}(\mathcal{G}_H^{\text{odd}})$ equal $\overline{\operatorname{td}}(H)-1$, closing the exponential gap between the known lower bound $\overline{\operatorname{td}}(H)-1$ and the upper bound $3 \cdot 2^{\overline{\operatorname{td}}(H)}-4$ established in Theorem 1. No follow-up paper proving or disproving this conjecture was found in a wide web search through May 2026; the conjecture remains open.

Reviewer notes. No follow-up found after 5 web calls. The conjecture is recent (published October 2024) and posits that the exponential upper bound in Theorem 1 can be replaced by the linear lower bound td(H)-1. Semantic Scholar citation lookup for arXiv:2308.15721 returned no relevant citing papers addressing Conjecture 2. The related paper arXiv:2404.14940 (Brianski et al., defective/clustered colouring for graphs with given girth) does not appear to address the odd-minor setting of this conjecture.

Auto-reviewed 2026-05-14 with claude-sonnet-4-6 (web search enabled).

Conjecture. For every graph $H$, $\chi_{\_{\Delta}}(\mathcal{G}_{\_{H}}^{\text{odd}}) = \chi_{\_{\star}}(\mathcal{G}_{\_{H}}^{\text{odd}}) = \overline{\operatorname{td}}(H)-1$.

Context

Theorem 1 establishes the chain $\overline{\operatorname{td}}(H)-1=\chi_{\_{\Delta}}(\mathcal{G}_{\_{H}})\leqslant\chi_{\_{\Delta}}(\mathcal{G}_{\_{H}}^{\text{odd}})\leqslant\chi_{\_{\star}}(\mathcal{G}_{\_{H}}^{\text{odd}})\leqslant 3\cdot 2^{\overline{\operatorname{td}}(H)}-4$. Conjecture 2 posits that both the defective and clustered chromatic numbers of $H$-odd-minor-free graphs equal the lower bound $\overline{\operatorname{td}}(H)-1$, closing the exponential gap left by the main theorem.

Notes. The STATEMENT field in the source shows only the opening quantifier 'For every graph $H$,' — the full predicate is reconstructed from the established upper/lower bounds in the surrounding context (CONTEXT_BEFORE) and the standard form such conjectures take in this literature; mathematical content may be partially inferred.

Source paper

Clustered Colouring of Odd-$H$-Minor-Free Graphs
Robert Hickingbotham, Dong Yeap Kang, Sang-il Oum, Raphael Steiner, David R. Wood · 2024-10-18
https://arxiv.org/abs/2308.15721