col★ characterization for minor-closed classes
Conjecture 4 · arXiv:1710.02727
Status open medium confidence
Conjecture 4 from arXiv:1710.02727 asserts that a minor-closed class satisfies col*(G) ≤ t if and only if it excludes K_{t,m} and I_{t-1}+P_m for some m. The source paper (Theorem 7) establishes the conjecture in the special case of minor-closed classes of bounded treewidth. No follow-up paper resolving the full conjecture was found in an exhaustive web search; the conjecture appears to remain open as of 2026.
Reviewer notes. The conjecture is from 2017 (part I of a planned series); no part II was found in the indexed literature. The bounded treewidth special case (Theorem 7 of the source paper) is proven therein. The related Norin–Scott paper arXiv:1708.02370 on clustered colouring in minor-closed classes predates 1710.02727 and does not address Conjecture 4. The conjecture would imply χ*_ℓ(G) = col*(G) for every minor-closed class. Confidence is medium rather than high because the conjecture is nearly 9 years old and absence of a resolution in web search is somewhat suspicious for an active research area.
Context
Observation 3 shows that any class $\mathcal{G}$ with $\mathrm{col}^\star(\mathcal{G}) \leq t$ can contain only finitely many graphs of the form $K_{t,m}$ or $I_{t-1}+P_m$; the conjecture asserts that this necessary condition is also sufficient for minor-closed classes. Theorem 7 confirms the conjecture for the special case of minor-closed classes of bounded treewidth, and Conjecture 4 would imply $\chi^\star_{\ell}(\mathcal{G}) = \mathrm{col}^\star(\mathcal{G})$ for every minor-closed class.
Notes. PDF source — '6∈' in the extraction is ∉; statement reads cleanly.
Source paper
Islands in minor-closed classes. I. Bounded treewidth and separators
Zdeněk Dvořák, Sergey Norin · 2017-10-07
https://arxiv.org/abs/1710.02727
PDF source