Browse › Combinatorics › 157 Graph coloring, clique minors, and Colin de Verdière invariants
A counterexample to the Colin de Verdière chromatic 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 the Colin de Verdière chromatic conjecture by constructing graphs whose chromatic number exceeds their Colin de Verdière invariant by more than one. The examples have independence number at most two. In fact, their ordinary fractional chromatic number also exceeds their Colin de Verdière invariant by more than one.
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.
Formalization
- OpenAI, Lean scope note for family 157 (
lean/docs/157.md) (openai/math release, 2026-10-06). The family's Lean scope note covers the Hadwiger counterexample and the list-coloring bound, and states that the Colin de Verdière consequence is outside the formalized statement. [family-level]
Possibly relevant literature (found by the agent, not checked)
- arXiv preprint, The Extremal Function and Colin de Verdière Graph Parameter (arXiv:1706.07451). Conjectures $|E(G)|\le t|V(G)|-\binom{t+1}{2}$ when $\mu(G)\le t$ and proves it in special cases, e.g. when the complement is chordal; this is edge-density context for dense graphs like those in Theorem 1.1, which have $\alpha(G)\le2$ and $\mu(G)<|V(G)|/2-1$.
Elsewhere
- VibeMathed: Problem record
- Emergent Mind: family 157
Independent sites; their content is not reviewed here.
Cite
@misc{OAI:A-counterexample-to-the-Colin-de-Verdiere-chromatic-conjecture-September-23-2026,
author = {{OpenAI}},
title = {{A counterexample to the Colin de Verdi{\`e}re chromatic conjecture}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/A-counterexample-to-the-Colin-de-Verdiere-chromatic-conjecture-September-23-2026/paper.pdf}{OAI:A-counterexample-to-the-Colin-de-Verdiere-chromatic-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 Hadwiger's conjecture · September 23, 2026
- A linear list-coloring bound in terms of the Hadwiger number · September 23, 2026