← All problems

Hadwiger conjecture (graph theory)

83 years old · traced to

Let GG be a finite loopless undirected graph. A graph HH is a minor of GG if HH can be obtained from a subgraph of GG by a sequence of edge contractions; equivalently, KtK_t is a minor of GG if and only if there are tt pairwise disjoint vertex sets V1,…,Vt⊆V(G)V_1,\dots,V_t \subseteq V(G), each inducing a connected subgraph of GG, such that for all i≠ji \neq j some edge of GG joins ViV_i to VjV_j. Let

h(G)=max⁡{ t≥1:Kt is a minor of G }h(G) = \max\{\, t \ge 1 : K_t \text{ is a minor of } G \,\}

and let χ(G)\chi(G) denote the chromatic number of GG, i.e. the least number of colours in a proper vertex colouring of GG.

For every finite loopless graph GG,

χ(G)≤h(G).\chi(G) \le h(G).

Equivalently, for every integer t≥1t \ge 1, every finite loopless graph with no KtK_t minor has a proper vertex colouring with t−1t-1 colours.

Equivalent formulations
  1. 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
  1. H. Hadwiger, "Über eine Klassifikation der Streckenkomplexe," Vierteljahrsschrift der Naturforschenden Gesellschaft in Zürich 88 (1943), 133-142.
  2. N. Robertson, P. Seymour and R. Thomas, "Hadwiger's conjecture for K_6-free graphs," Combinatorica 13 (1993), 279-361.
  3. A. V. Kostochka, "Lower bound of the Hadwiger number of graphs by their average degree," Combinatorica 4 (1984), 307-316.
  4. 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.
  5. Wikipedia, Hadwiger conjecture (graph theory), the article this problem comes from.

Source: Wikipedia

Progress summary

Refreshed
Open · progress reported

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 t≤3t\le 3 in 1943.
  • Wagner reduced the t=4t=4 case to the Four Colour Theorem; Appel and Haken proved that theorem in 1976.
  • Robertson, Seymour, and Thomas proved the t=5t=5 case in 1993.
  • The t=6t=6 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 χ(G)≤h(G)\chi(G)\le h(G) 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 K5K_5 are settled, K6K_6 and the general conjecture remain open, and Murthy's claimed general proof is unverified.

Sources

Solutions 2

Claimed by OpenAI.See full solutionHide 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

Manuscript: https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/A-counterexample-to-Hadwigers-conjecture-September-23-2026/paper.pdf

  • OpenAI-157-01-A-counterexample-to-Hadwiger-s-conjecture.pdf956,260 bytesOpen
Claimed by OpenAI.See full solutionHide 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

Manuscript: https://github.com/openai/math/blob/adc7f1241b42e322a6451854ab7e4b4c146bf78a/preprints/A-linear-list-coloring-bound-in-terms-of-the-Hadwiger-number-September-23-2026/paper.pdf

  • OpenAI-157-03-A-linear-list-coloring-bound-in-terms-of-the-Hadwiger-number.pdf587,502 bytesOpen