A counterexample to Hadwiger's conjecture
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.
Comments and reviews
No comments yet.
Discussed elsewhere
There was (maybe not a very solid) consensus, and maybe more, hope, that Hadwiger's conjecture would provide a nice upper bound for the chromatic number $\chi(G)$ of a graph $G$ , but if I am not mistaken, OpenAI constructed a counterexample .
API
curl /api/v1/records/openai-math/A-counterexample-to-Hadwigers-conjecture
curl -X POST /api/v1/records/openai-math/A-counterexample-to-Hadwigers-conjecture/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/openai-math/A-counterexample-to-Hadwigers-conjecture/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'
Updates: Sharing AI progress on mathematics (amazing!); and my lecture plansCombinatorics and moreOct 7, 2026
gives counterexamples to the original conjecture, even among graphs with independence number at most two. The chromatic number of the plane. In 2018 I reported Aubrey de Grey’s breakthrough showing that five colors are necessary to avoid monochromatic pairs at distance one. The new manuscript…