{"id":"openai-math/A-counterexample-to-Hadwigers-conjecture","pdf":"https://github.com/openai/math/blob/main/preprints/A-counterexample-to-Hadwigers-conjecture-September-23-2026/paper.pdf","url":"https://github.com/openai/math/tree/main/preprints/A-counterexample-to-Hadwigers-conjecture-September-23-2026","tags":["graph-coloring","hadwiger-conjecture","extremal-graph-theory","chromatic-number"],"score":0,"title":"A counterexample to Hadwiger's conjecture","domain":"Combinatorics","family":"157","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"math.CO","summary":"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.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":2,"published":"2026-09-23","reactions":{},"discussion":[{"url":"https://gilkalai.wordpress.com/2026/10/07/updates-sharing-ai-progress-on-mathematics-amazing-and-my-lecture-plans/#:~:text=gives%20counterexamples%20to%20the%20original%20conjecture%2C%20even%20among%20graphs%20with%20independence%20number%20at%20most%20two","date":"2026-10-07","kind":"web","site":"Combinatorics and more","text":"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…","added":"2026-10-24","title":"Updates: Sharing AI progress on mathematics (amazing!); and my lecture plans"},{"url":"https://mathoverflow.net/a/516005","date":"2026-10-13","kind":"web","site":"mathoverflow.net","text":"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 .","added":"2026-10-24","title":"Answer to: Which of the results released by OpenAI went against the conventional mathematical wisdom?","author":"Dominic van der Zypen"}],"formalized":true,"family_title":"Graph coloring, clique minors, and Colin de Verdière invariants"}