Hadwiger conjecture (graph theory)
Let be a finite loopless undirected graph. A graph is a minor of if can be obtained from a subgraph of by a sequence of edge contractions; equivalently, is a minor of if and only if there are pairwise disjoint vertex sets , each inducing a connected subgraph of , such that for all some edge of joins to . Let
and let denote the chromatic number of , i.e. the least number of colours in a proper vertex colouring of .
For every finite loopless graph ,
Equivalently, for every integer , every finite loopless graph with no minor has a proper vertex colouring with colours.
Equivalent formulations
In combinatorial geometry, the Hadwiger conjecture states that any convex body in n-dimensional Euclidean space can be covered by 2n or fewer smaller bodies homothetic with the original body, and that furthermore, the upper bound of 2n is necessary if and only if the body is a parallelepiped. There also exists an equivalent formulation in terms of the number of floodlights needed to illuminate the body.
source: Wikipedia
References
- H. Hadwiger, "Über eine Klassifikation der Streckenkomplexe," Vierteljahrsschrift der Naturforschenden Gesellschaft in Zürich 88 (1943), 133-142.
- N. Robertson, P. Seymour and R. Thomas, "Hadwiger's conjecture for K_6-free graphs," Combinatorica 13 (1993), 279-361.
- A. V. Kostochka, "Lower bound of the Hadwiger number of graphs by their average degree," Combinatorica 4 (1984), 307-316.
- S. Norin, L. Postle and Z.-X. Song, "Breaking the degeneracy barrier for coloring graphs with no K_t minor," Advances in Mathematics 422 (2023), 109020.
- Wikipedia, Hadwiger conjecture (graph theory), the article this problem comes from.
Source: Wikipedia
Progress summary
A 2022 paper claims a complete proof, but it has not been independently verified, so the problem remains open.
Hadwiger posed the conjecture in 1943: every finite graph should have chromatic number at most the size of its largest complete minor. It generalizes the Four Colour Theorem and remains unresolved beyond the established low cases.
Known results
- Hadwiger proved the cases in 1943.
- Wagner reduced the case to the Four Colour Theorem; Appel and Haken proved that theorem in 1976.
- Robertson, Seymour, and Thomas proved the case in 1993.
- The case remains open; quantitative coloring bounds and restricted graph-class results are known but do not prove the conjecture.
web.math.princeton.edu · en.wikipedia.org
April 2022 claimed proof
T. Srinivasa Murthy's paper, in a version dated April 22, 2022, claims to prove for every simple graph using finite-field algebra. The retrieved sources provide no independent verification, so this is a claimed resolution rather than an established theorem.
Current status (as of September 2026): The cases through are settled, and the general conjecture remain open, and Murthy's claimed general proof is unverified.
Solutions 2
Claimed by OpenAI.See full solution
Claims arbitrarily large graphs of independence number at most two whose chromatic number, and even ordinary fractional chromatic number, exceed their Hadwiger number.
Repository: https://github.com/openai/math
- OpenAI-157-01-A-counterexample-to-Hadwiger-s-conjecture.pdfOpen
Claimed by OpenAI.See full solution
Claims the list chromatic number of every finite nonempty simple graph is at most C times its largest clique-minor order for a universal constant C, and hence chi(G)<=C h(G). This is a constant-factor bound, not the factor-one Hadwiger conclusion chi(G)<=h(G).
GitHub repository: https://github.com/openai/math
- OpenAI-157-03-A-linear-list-coloring-bound-in-terms-of-the-Hadwiger-number.pdfOpen