VibeMathedMath problems solved with AI
Sign in

The Colin de Verdiere Chromatic Conjecture

Colin de Verdiere (1990) introduced the graph invariant μ(G)\mu(G): the maximum nullity of a real symmetric matrix that is negative on edges, zero on non-edges, has exactly one negative eigenvalue and satisfies the Strong Arnold Property. It characterizes outerplanar (μ≤2\mu\le2), planar (μ≤3\mu\le3) and linklessly embeddable (μ≤4\mu\le4) graphs. He conjectured that χ(G)≤μ(G)+1\chi(G)\le\mu(G)+1 for every graph; since h(G)≤μ(G)+1h(G)\le\mu(G)+1, this is implied by Hadwiger's conjecture, and it holds when μ(G)≤4\mu(G)\le4. Does every finite graph satisfy χ(G)≤μ(G)+1\chi(G)\le\mu(G)+1?

Result
Disproved(see note)
Status
Candidate (review pending)
AI contribution
AI-discovered
Method
Construction
Field
Spectral graph theory, graph coloring
Posed by
Yves Colin de Verdiere, Sur un nouvel invariant des graphes et un critere de planarite, J. Combin. Theory Ser. B 50 (1990)
Year posed
1990
Years open
36y
Solved
2026-09-23
Model
Unreleased internal OpenAI model
Vendor
OpenAI
Collaborators
—
Verification
Unreviewed
Publication
Announced
Collection
OpenAI math release (October 2026), version adc7f12
Significance
30 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Theorem 1.1: there are graphs of arbitrarily large order with α(G)≤2\alpha(G)\le2 and μ(G)+1<∣V(G)∣/2≤χ(G)\mu(G)+1<|V(G)|/2\le\chi(G); the fractional chromatic number also exceeds μ(G)+1\mu(G)+1. The proof shows every well-signed matrix on the graph with one negative eigenvalue has rank above ∣V(G)∣/2+1|V(G)|/2+1, without using the Strong Arnold Property, so the Lovasz-Schrijver parameter κ\kappa also satisfies κ(G)+1<∣V(G)∣/2\kappa(G)+1<|V(G)|/2. Since h≤μ+1h\le\mu+1, these graphs also violate Hadwiger's inequality, by a route independent of the connected-matching companion. Nothing is claimed for small μ\mu.

What the AI did

Produced by an unreleased internal OpenAI model as part of an OpenAI evaluation on open research problems. The release README says the vast majority of results used one fixed procedure, averaging about three hours of ChatGPT Pro thinking compute per result; this result is not among the README's stated exceptions (the Riemann zeta zero-free region work and the Hodge conjecture for CM abelian varieties). The manuscript is authored as OpenAI with no human author named. The README also cautions that unformalized results could have issues.

Verification

No independent mathematician has checked this yet. Checked here: the abstract, introduction and Theorem 1.1, read against the conjecture as cited (Colin de Verdiere 1990, 1998; van der Holst-Lovasz-Schrijver 1999). The construction and rank argument were not refereed. formalization.yaml lists no main result for this manuscript. Examples exist only at large order; the paper notes the conjecture remains true where mu is at most 4.

Sources

Changelog1 change

Discussion