Gerards–Seymour odd Hadwiger conjecture

From papers

Let GG be a graph. We say that GG has KtK_t as an odd minor if there exist vertex-disjoint trees T1,,TtGT_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 iji\ne j there are vertices xiV(Ti)x_i\in V(T_i) and xjV(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.

Progress summary

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

Sources & referencesView supporting material

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.

Solutions 0

No solutions have been posted yet.