Gerards–Seymour odd Hadwiger conjecture

About 11 years old · traced to

Let GG be a graph. We say that GG has KtK_t as an odd minor if there exist vertex-disjoint trees T1,…,Tt⊆GT_1,\dots,T_t\subseteq G and functions

χi:V(Ti)→{black,white}\chi_i:V(T_i)\to\{\text{black},\text{white}\}

for which each χi\chi_i is a proper 22-coloring of TiT_i, and for every i≠ji\ne j there are vertices xi∈V(Ti)x_i\in V(T_i) and xj∈V(Tj)x_j\in V(T_j) with {xi,xj}∈E(G)\{x_i,x_j\}\in E(G) and χi(xi)=χj(xj)\chi_i(x_i)=\chi_j(x_j).

Odd Hadwiger conjecture. If

χ(G)≥t,\chi(G)\geq t,

then GG has KtK_t as an odd minor. Equivalently, if GG does not have KtK_t as an odd minor, then

χ(G)<t.\chi(G)<t.

Gerards and Seymour proposed this parity-sensitive strengthening of Hadwiger's conjecture. The paper disproves it: for every fixed δ>0\delta>0 and all sufficiently large tt, there is a graph with χ(G)≥(32−δ)t\chi(G)\geq(\frac32-\delta)t having no KtK_t odd minor.

References

Primary source

Marcus Kühn, Lisa Sauermann, Raphael Steiner and Yuval Wigderson, “Disproof of the Odd Hadwiger Conjecture”, arXiv:2512.20392 (2025).

Additional references

5 papers in this index state this conjecture (2015–2025). The statement above is taken from the most recent of them; the others are arXiv:2509.00929, arXiv:2505.02812, arXiv:2203.02766, arXiv:1508.04053.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.