TOPICS
Search

Odd Hadwiger Conjecture


The odd Hadwiger conjecture, proposed by Gerards and Seymour (Jensen and Toft 1995), is a strengthening of the Hadwiger conjecture. It states that, if a graph G has chromatic number chi(G)>=t, then G has the complete graph K_t as an odd minor. Here, an odd K_t minor consists of t vertex-disjoint trees T_1, ..., T_t in G, each properly 2-colored, such that every pair of trees is joined by an edge whose endpoints have the same color.

The conjecture is true for t=3 and t=4, and the case t=5 is a strengthening of the four-color theorem (Kühn et al. 2025). However, the conjecture was disproved by Kühn et al. (2025), who constructed graphs with no odd K_t minor and chromatic number at least (3/2-o(1))t for sufficiently large t. The disproof of the odd Hadwiger conjecture does not disprove the Hadwiger conjecture itself, which remains open for larger values of t.


See also

Chromatic Number, Complete Graph, Graph Minor, Hadwiger Conjecture

Explore with Wolfram|Alpha

References

Jensen, T. R. and Toft, B. Graph Coloring Problems. New York: Wiley, 1995.Kühn, M.; Sauermann, L.; Steiner, R.; and Wigderson, Y. "Disproof of the Odd Hadwiger Conjecture." 23 Dec 2025. https://arxiv.org/abs/2512.20392.

Cite this as:

Weisstein, Eric W. "Odd Hadwiger Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/OddHadwigerConjecture.html

Subject classifications