Browse › Combinatorics › 157 Graph coloring, clique minors, and Colin de Verdière invariants
A linear list-coloring bound in terms of the Hadwiger number
Open PDFCite Report a problem Add a reference or comment Interested in working on this Start a discussion
Edit NOTES.md · Existing issues · Source on GitHub
Abstract
We prove that every finite nonempty graph G satisfies $\chi_{\mathrm{list}}(G)\le C h(G)$ for an absolute integer C, where $h(G)$ is the largest order of a clique minor. This resolves the Linear List Hadwiger conjecture affirmatively.
If the PDF does not display here, open it directly: Open PDF.
Notes
No notes yet. Add a reference, a comment or your name with the buttons above, or edit NOTES.md on GitHub.
Automatically collected notes (unreviewed)
work in progress
Collected automatically by AI tools (Claude Opus 5.5 and GPT-6 Astra, 2026-10-21) and not checked by a person. May be wrong or incomplete. Report an error.
Follow-up works
- Yangyan Gu, Rongxing Xu, A shorter proof of the linear list Hadwiger conjecture (arXiv:2610.01946v2, revised 2026-10-12). Revised version of a paper whose v1 this manuscript cites; it gives a simpler proof of a weaker form of this paper's Proposition 3.1 (graphs on at most $t(\ln t)^5$ vertices) and reuses its thinning argument as Lemma 2.9 to give a shorter proof of the conjecture.
Formalization
- OpenAI, Lean scope note for family 157 (
lean/docs/157.md) (openai/math release, 2026-10-06). The release's formalization proves the existence of one integer $C\ge1$ with $\chi_{\mathrm{list}}(G)\le C\,h(G)$ for all finite nonempty simple graphs (comparator fileListHadwiger.lean). [family-level] - anxkhn, feat(Paper): add the linear list-Hadwiger bound, google-deepmind/formal-conjectures PR #6981 (opened 2026-10-08, open). Adds this paper's Theorem 1.1 as a formal-conjectures statement pinned to the release; a reviewer found no statement mismatch but reports Comparator and compilation compatibility failures, and the PR is not yet approved.
- Sergey Norin and Raphael Steiner, Linear Hadwiger's conjecture in Lean (GitHub; README reports a build on 2026-09-25). This separate development formalizes their ordinary-coloring bound, corresponding to the type of conclusion in Corollary 1.2 rather than the arbitrary-list theorem, and attributes the formalization to Codex under the authors' guidance. [AI-generated per source]
Possibly relevant literature (found by the agent, not checked)
- Sergey Norin, Raphael Steiner, A Proof of the Linear Hadwiger Conjecture (arXiv:2610.05291, 2026-10-04). Independently proves that $K_t$-minor-free graphs are $Ct$-colorable, the ordinary bound in Corollary 1.2, and its Section 4 identifies the absence of a list-coloring analogue of their Lemma 13 as an obstacle to extending the method; its abstract states the proof "was found by GPT-6 Astra, following the directions by the authors". [AI-generated per source]
- David R. Wood, Tweaking the constant in the Linear Hadwiger Theorem (arXiv:2610.10831, 2026-10). Optimizes the Norin–Steiner argument to the explicit constant 1,118,430 for the ordinary linear bound, whereas the constant in this paper's Theorem 1.1 is not computed; its AI-use statement reports using Claude Opus 5.5 and GPT-6.
Elsewhere
- VibeMathed: Problem record
- Emergent Mind: family 157
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:A-linear-list-coloring-bound-in-terms-of-the-Hadwiger-number-September-23-2026,
author = {{OpenAI}},
title = {{A linear list-coloring bound in terms of the Hadwiger number}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/A-linear-list-coloring-bound-in-terms-of-the-Hadwiger-number-September-23-2026/paper.pdf}{OAI:A-linear-list-coloring-bound-in-terms-of-the-Hadwiger-number-September-23-2026}},
year = {2026}
}Lean formalization
OpenAI provides Lean files for this family: lean/docs/157.md. The Lean statements have not been checked by people against the paper's claims.
Family 157: Graph coloring, clique minors, and Colin de Verdière invariants
Disproves Hadwiger's conjecture even for fractional coloring: arbitrarily large finite simple graphs with independence number at most two satisfy $\chi_f(G)\gt h(G)$, where $h(G)$ is the largest clique-minor order. Also disproves the fractional Colin de Verdière chromatic bound $\chi_f(G)\le\mu(G)+1$. In the positive direction, every finite nonempty graph satisfies $\chi_{\mathrm{list}}(G)\le C h(G)$ for a universal constant C.
Other papers in this family:
- A counterexample to Hadwiger's conjecture · September 23, 2026
- A counterexample to the Colin de Verdière chromatic conjecture · September 23, 2026