Browse › Combinatorics › 157 Graph coloring, clique minors, and Colin de Verdière invariants
A counterexample to Hadwiger's conjecture
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 disprove Hadwiger's conjecture by constructing arbitrarily large graphs whose chromatic number exceeds their Hadwiger number. The examples have independence number at most two, and even their ordinary fractional chromatic number exceeds their Hadwiger number. Thus they also disprove the fractional-coloring weakening discussed by Reed and Seymour.
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-23) and not checked by a person. May be wrong or incomplete. Report an error.
Comments and discussion
- Gil Kalai, Updates: Sharing AI progress on mathematics (amazing!); and my lecture plans, Combinatorics and more (blog, 2026-10-07). Lists this paper among the release's results, saying it "gives counterexamples to the original conjecture, even among graphs with independence number at most two", and notes the earlier disproof of the odd-minor strengthening.
Formalization
- OpenAI, Lean scope note for family 157 (
lean/docs/157.md) (openai/math release, 2026-10-06). The release's formalization proves $h(G)<26m/75+2/3<m/2\le\chi(G)$ for arbitrarily large graphs with $\alpha(G)\le2$; the fractional strengthening and the Colin de Verdière consequence are stated to be outside its scope. [family-level] - Edouard Bonnet, hadwiger-counterexample (GitHub; local kernel replay reported 2026-10-11). Lean development that vendors the release's construction and, per its README, also derives the fractional-chromatic consequence (
FractionalCounterexample.lean); submitted to the Lax archive aslax-342547.
Related prior literature mentioned by others
- Marcus Kühn, Lisa Sauermann, Raphael Steiner, Yuval Wigderson, Disproof of the Odd Hadwiger Conjecture (arXiv:2512.20392, 2025-12-23). Earlier disproof of the odd-minor strengthening, which Kalai's post connects to this result (the manuscript also cites it).
- Freddie Illingworth and Raphael Steiner, Disproof of the dominating Hadwiger conjecture (arXiv:2609.35361, 2026-09-28). Xie's survey, Section 8.3.3, compares this AI-discovered construction with the manuscript's independence-two examples while distinguishing dominating clique models from ordinary clique minors. [AI-generated per source]
Possibly relevant literature (found by the agent, not checked)
- Jofre Costa, Eric Luu, David R. Wood, Jung Hon Yip, Verifying Hadwiger's Conjecture for Examples of Graphs with α(G) = 2 (arXiv:2512.17114, 2025-12-18). Surveys and extends tools for Hadwiger's conjecture in the $\alpha(G)=2$ setting of Theorem 1.1 and proves variants for inflations of specific graph classes.
- António Girão, Sergey Norin, Youri Tamitegama, Jane Tan, Two Relaxations of the Dominating Hadwiger's Conjecture (arXiv:2608.12126, 2026-08-12). Studies the Illingworth–Wood dominating strengthening of Hadwiger's conjecture, which Corollary 1.2 would also refute if correct.
Digests and expositions
- Ying Xie, What the Machine Invented: Mining New Mathematical Instruments from OpenAI's October 2026 Release of AI-Generated Mathematics (arXiv:2610.17090, 2026-10-12). Section 8.3.3 describes the hole relation, the entropy-minimizing container argument and the collision machinery, rating the method "new" and noting that "the argument gives neither an explicit graph nor an explicit clique-minor number"; the survey states it did not compile the Lean development. [AI-generated per source]
News and blogs
- Azmat, Hadwiger Conjecture: How OpenAI's Counterexample Proof Breaks an 83-Year-Old Coloring Rule (BinaryVerse AI, 2026-10-18). Explains the manuscript's parity construction, four-hole obstruction and connected-matching bound, and distinguishes the documented ordinary-counterexample formalization from the fractional-coloring claim.
Elsewhere
- VibeMathed: Problem record
- VibeMathed: Problem record
- Emergent Mind: family 157
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:A-counterexample-to-Hadwigers-conjecture-September-23-2026,
author = {{OpenAI}},
title = {{A counterexample to Hadwiger's conjecture}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/A-counterexample-to-Hadwigers-conjecture-September-23-2026/paper.pdf}{OAI:A-counterexample-to-Hadwigers-conjecture-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 the Colin de Verdière chromatic conjecture · September 23, 2026
- A linear list-coloring bound in terms of the Hadwiger number · September 23, 2026