Colin de Verdière’s chromatic-number conjecture
Follow the latest progress by email.
Does every finite graph G satisfy χ(G)≤μ(G)+1, relating its chromatic number to its Colin de Verdière invariant? The proposed counterexample setting includes independence number at most two.
Why it matters and what counts as progress
Why it matters: The proposed inequality ties a spectral graph invariant to coloring, beyond the low-invariant cases previously established.
What counts as progress: Prove the inequality in new graph classes or construct a graph with χ(G)>μ(G)+1 and establish both invariants.
How the problem developed
- 1990 · Invariant and conjecture [1]
Yves Colin de Verdière Introduced the spectral graph invariant μ and conjectured χ(G)≤μ(G)+1; the conjecture would imply the four-colour theorem.
- 1993 · Partial result [2]
Neil Robertson, Paul Seymour and Robin Thomas Proved Hadwiger’s conjecture for K₆-minor-free graphs, which implies χ(G)≤μ(G)+1 when μ(G)≤4.
- 23 Sept 2026 · Reported counterexample [3]
OpenAI Reported finite graphs with arbitrarily large chromatic number that violate χ(G)≤μ(G)+1.
AI contribution
A counterexample to the Colin de Verdière chromatic conjecture
The manuscript claims arbitrarily large finite graphs G with independence number at most two and μ(G)+1<|V(G)|/2≤χ(G), contradicting the proposed inequality χ(G)≤μ(G)+1.
Sources
- Yves Colin de Verdière · Sur un nouvel invariant des graphes et un critère de planarité (1990)
- Robertson, Seymour and Thomas · Hadwiger’s conjecture for K₆-free graphs (1993)
- OpenAI, Colin de Verdière counterexample manuscript
- A counterexample to the Colin de Verdière chromatic conjecture
- OpenAI Math release provenance
Website timeline
Publication dates and editorial changes.
OpenAI reports counterexamples to the Colin de Verdière chromatic conjecture