Clique-minor constants left open by the disproof of the odd Hadwiger conjecture: the Duchet–Meyniel constant at independence number two and the 3/2 odd-minor separation ratio in general graphs

The disproof of the odd Hadwiger conjecture by Kühn, Sauermann, Steiner and Wigderson (arXiv:2512.20392) left open two precisely bracketed constants that govern how far the chromatic number of a graph can exceed the order of its largest clique minor. First, for ordinary minors in graphs of independence number two, the 1982 Duchet–Meyniel theorem guarantees only a clique minor of order $\lceil n/3\rceil$, Fox's improvement is sublinear, and the conjectured truth is $\lceil n/2\rceil$ (equivalent, by Plummer–Stiebitz–Toft, to Hadwiger's conjecture in this class): is the constant $1/3$ improvable by a linear amount, or is it asymptotically tight — the latter being strictly stronger than refuting Hadwiger's conjecture for graphs of independence number two? Second, for odd minors with no restriction on independence number, the disproof achieves a chromatic-to-odd-minor-order ratio of $3/2-o(1)$, Proposition 1.5 of the disproof caps the ratio at $3/2$ whenever $\alpha(G)\le 2$, and Hadwiger's conjecture would cap it at $2$: can the ratio exceed $3/2$ for graphs with $\alpha(G)\ge 3$, or does a universal $(3/2+o(1))$ bound hold? The problem asks to determine both constants; as of August 2026 both remain open, most recently reaffirmed by Bermúdez–Netto–Quiroz (arXiv:2608.15302), who state that it is still open whether any constant $c>1/3$ works in the Duchet–Meyniel setting.

Background

Hadwiger's conjecture, formulated in 1943, is one of the central open problems of graph theory (see Seymour's 2016 survey for its history and status). It asserts that every graph $G$ with chromatic number $\chi(G)\ge t$ contains the complete graph $K_t$ on $t$ vertices as a minor. A minor is obtained from $G$ by deleting vertices, deleting edges, and contracting edges (merging the two endpoints of an edge); equivalently, $G$ has $K_t$ as a minor if it contains $t$ pairwise vertex-disjoint connected subgraphs, called branch sets, every two of which are joined by at least one edge. The largest such $t$ is the Hadwiger number of $G$. The conjecture vastly generalizes the Four-Color Theorem, is verified only for $t\le 6$, and remains open in general; the best known weakening, due to Delcourt and Postle, states that every graph with no $K_t$ minor has chromatic number at most $Ct\log\log t$ for an absolute constant $C$. In 1993, Gerards and Seymour proposed a parity-strengthened variant. A graph $G$ contains $K_t$ as an odd minor if there exist vertex-disjoint trees $T_1,\dots,T_t\subseteq G$ and proper black/white 2-colorings of each tree such that, for every pair $i\ne j$, some edge of $G$ joins two vertices of the same color, one in $T_i$ and one in $T_j$. Equivalently, $H$ is an odd minor of $G$ if $H$ can be obtained from $G$ by deleting vertices and edges and repeatedly contracting all edges of an edge-cut; the notion tracks the parity structure of the graph — for instance, a graph is bipartite if and only if it contains no odd $K_3$ minor. The odd Hadwiger conjecture asserted that every graph $G$ with $\chi(G)\ge t$ contains $K_t$ as an odd minor; it was known for $t\le 4$, with the case $t=5$ having only an announced, unpublished proof. Shortly before its disproof, Steiner proved that the ordinary and odd conjectures are asymptotically equivalent up to a factor of two: whenever every graph with no $K_t$ minor has chromatic number below $f(t)$, every graph with no odd $K_t$ minor has chromatic number below $2f(t)$.

The disproof. Kühn, Sauermann, Steiner and Wigderson constructed graphs with chromatic number at least $(3/2-o(1))t$ that contain no odd $K_t$ minor, refuting the odd Hadwiger conjecture in a strong quantitative form. Their counterexamples have independence number $\alpha(G)=2$, where $\alpha(G)$ denotes the maximum size of an independent set (a set of pairwise non-adjacent vertices). This parameter regime has long been the standard testing ground for Hadwiger-type questions: in a graph with $\alpha(G)\le 2$ on $n$ vertices, every color class has size at most two, so $\chi(G)\ge\lceil n/2\rceil$, and Hadwiger's conjecture then predicts a clique minor of order $\lceil n/2\rceil$. Plummer, Stiebitz and Toft proved that for graphs with $\alpha(G)=2$ Hadwiger's conjecture is equivalent to the statement that every $n$-vertex such graph contains a $K_{\lceil n/2\rceil}$ minor; Ji, Song, Weiss and Zhang proved the analogous equivalence for odd minors. Duchet and Meyniel showed in 1982 that every $n$-vertex graph with $\alpha(G)=2$ contains a clique minor of order $\lceil n/3\rceil$; their argument, and Fox's later improvement of the bound by a sublinear amount, works through connected matchings (matchings in which every two edges are joined by an edge — a connected matching of size $s$ directly yields a $K_s$ minor by taking the matching edges as two-vertex branch sets). No linear improvement of the constant $1/3$ is known, and Seymour's 2016 problem list singles this constant out as a major open problem. For odd minors, Kawarabayashi and Song extended the Duchet–Meyniel theorem: every $n$-vertex graph with $\alpha(G)=2$ contains an odd clique minor of order $\lceil n/3\rceil$. Theorem 1.4 of the disproof paper shows that this is asymptotically best possible (for every $\eta>0$ and all large $n$ there are $n$-vertex graphs with $\alpha(G)\le 2$ containing no odd $K_t$ minor for any $t\ge(1/3+\eta)n$), and its Proposition 1.5 shows that within the family $\alpha(G)\le 2$ the ratio between $\chi(G)$ and the largest odd clique-minor order $t$ is at most $3/2$ up to rounding ($\chi(G)\le\lceil\frac{3}{2}(t-1)\rceil$), matching the $(3/2-o(1))$ lower bound. In the unrestricted setting, Steiner's equivalence combined with Delcourt–Postle gives $\chi(G)\le 2Ct\log\log t$ for graphs with no odd $K_t$ minor, and Hadwiger's conjecture itself would imply $\chi(G)<2t$; no constant upper bound is known unconditionally. After the disproof, the quantitative picture therefore contains two precisely bracketed gaps, and closing them is the problem stated below.

Problem Statement

Determine the two asymptotic constants that the disproof of the odd Hadwiger conjecture left open, namely how far the chromatic number of a graph can exceed the order of its largest clique minor — for ordinary minors at independence number two, and for odd minors in unrestricted graphs.

(a) The Duchet–Meyniel constant for ordinary clique minors at independence number two. Let $c^{\star}$ be the supremum of the constants $c$ such that, for all sufficiently large $n$, every $n$-vertex graph $G$ with $\alpha(G)=2$ contains $K_{\lceil cn\rceil}$ as a minor (graphs with $\alpha(G)\le 2$ that are not complete have $\alpha(G)=2$ exactly, so the $\alpha\le 2$ variant is the same question). The Duchet–Meyniel theorem gives $c^{\star}\ge 1/3$, Fox's theorem adds only a sublinear term, and by the Plummer–Stiebitz–Toft equivalence the value $c^{\star}=1/2$ is exactly Hadwiger's conjecture for graphs of independence number two. Determine whether $c^{\star}>1/3$: either (i) prove that for some fixed $\varepsilon>0$, every sufficiently large $n$-vertex graph with $\alpha(G)=2$ contains a clique minor of order at least $(1/3+\varepsilon)n$ — the first linear improvement of the 1982 bound; or (ii) prove that $c^{\star}=1/3$, that is, construct for every $\varepsilon>0$ and all sufficiently large $n$ an $n$-vertex graph with $\alpha(G)=2$ containing no $K_{(1/3+\varepsilon)n}$ minor — which would refute Hadwiger's conjecture for graphs of independence number two. (The odd-minor analogue of (ii) is already known: Theorem 1.4 of the source shows that the odd $\lceil n/3\rceil$ bound of Kawarabayashi–Song is asymptotically tight.)

(b) The chromatic-versus-odd-minor separation ratio in unrestricted graphs. Let $oh(G)$ denote the odd Hadwiger number of $G$, the largest $t$ such that $G$ contains $K_t$ as an odd minor, and let $r^{\star}$ be the infimum, in the extended reals (possibly $+\infty$), of the real numbers $r$ for which there exists a single function $\delta(t)$ with $\delta(t)\to 0$ as $t\to\infty$ such that, for every integer $t\ge 1$ and every graph $G$ with no odd $K_t$ minor, $\chi(G)\le(r+\delta(t))t$; that is, the $o(1)$ term tends to zero as $t\to\infty$ uniformly over all such graphs $G$. The disproof shows $r^{\star}\ge 3/2$; Proposition 1.5 of the disproof shows that within the family $\alpha(G)\le 2$ the ratio never exceeds $3/2$ up to rounding; Hadwiger's conjecture, via Steiner's asymptotic equivalence, would give $r^{\star}\le 2$; unconditionally no constant upper bound is known. Determine whether $r^{\star}>3/2$: either (i) exhibit, for some fixed $\varepsilon>0$ and arbitrarily large $t$, graphs $G$ with $\chi(G)\ge(3/2+\varepsilon)t$ and no odd $K_t$ minor — necessarily with $\alpha(G)\ge 3$; or (ii) prove that every graph with no odd $K_t$ minor satisfies $\chi(G)\le(3/2+o(1))t$, showing that $3/2$ is the correct constant replacing the refuted odd Hadwiger conjecture.

The two parts are the two halves of one quantitative question: the disproof pinned the chromatic-to-clique-minor separation exactly in the (odd minors, $\alpha\le 2$) corner of the landscape, and this problem asks whether each of the two tight constants $1/3$ and $3/2$ survives when one of the two restrictions is dropped — the oddness of the minor in part (a), the independence-number bound in part (b). A complete answer determines both constants; each part also has independent value. The motivating parent question — whether a counterexample to Hadwiger's conjecture itself can be constructed, for instance by extending the source's randomized method past the two obstructions it isolates (the numerical obstruction that union bounds for ordinary minors would need edge-density $p\gg n^{-1/4}$, incompatible with the triangle-deletion constraint $p\le c/\sqrt{m}$, and the structural obstruction that ordinary-minor branch sets must be connected, while contracting the color classes of any optimal coloring yields a 'weak minor' of order $\chi(G)$) — is the famous Hadwiger conjecture and is deliberately not part of this problem's completion boundary.

References

1. Marcus Kühn, Lisa Sauermann, Raphael Steiner, Yuval Wigderson, Disproof of the Odd Hadwiger Conjecture, arXiv:2512.20392 (2025), doi:10.48550/arXiv.2512.20392, https://arxiv.org/abs/2512.20392
2. P. Duchet, H. Meyniel, On Hadwiger's Number and the Stability Number, in Graph theory (Cambridge, 1981), North-Holland Mathematics Studies 62, North-Holland (1982) 71–73, doi:10.1016/S0304-0208(08)73549-7, https://doi.org/10.1016/S0304-0208(08)73549-7
3. Ken-ichi Kawarabayashi, Zi-Xia Song, Some remarks on the odd Hadwiger's conjecture, Combinatorica 27 (2007) 429–438, doi:10.1007/s00493-007-2213-9, https://doi.org/10.1007/s00493-007-2213-9
4. Jacob Fox, Complete Minors and Independence Number, SIAM Journal on Discrete Mathematics 24 (2010) 1313–1321, doi:10.1137/090766814, https://doi.org/10.1137/090766814
5. Paul Seymour, Hadwiger's Conjecture, in Open Problems in Mathematics, Springer, Cham (2016) 417–437, doi:10.1007/978-3-319-32162-2_13, https://doi.org/10.1007/978-3-319-32162-2_13
6. Michael D. Plummer, Michael Stiebitz, Bjarne Toft, On a special case of Hadwiger's conjecture, Discussiones Mathematicae Graph Theory 23 (2003) 333–363, doi:10.7159/dmgt.1206, https://doi.org/10.7159/dmgt.1206
7. Raphael Steiner, Asymptotic equivalence of Hadwiger's conjecture and its odd minor-variant, Journal of Combinatorial Theory, Series B 155 (2022) 45–51, doi:10.1016/j.jctb.2022.02.002, https://doi.org/10.1016/j.jctb.2022.02.002
8. Michelle Delcourt, Luke Postle, Reducing linear Hadwiger's conjecture to coloring small graphs, Journal of the American Mathematical Society 38 (2025) 481–507, doi:10.1090/jams/1047, https://doi.org/10.1090/jams/1047
9. Yuqing Ji, Zi-Xia Song, Evan Weiss, Xia Zhang, Odd clique minors in graphs with independence number two, arXiv:2505.07727 (2025), doi:10.48550/arXiv.2505.07727, https://arxiv.org/abs/2505.07727
10. Jofre Costa, Eric Luu, David R. Wood, Jung Hon Yip, Verifying Hadwiger's Conjecture for Examples of Graphs with α(G)=2, arXiv:2512.17114 (2025), doi:10.48550/arXiv.2512.17114, https://arxiv.org/abs/2512.17114
11. Antonia Bermúdez, Bruno L. Netto, Daniel A. Quiroz, Odd minors or odd immersions in graphs with independence number two, arXiv:2608.15302 (2026), doi:10.48550/arXiv.2608.15302, https://arxiv.org/abs/2608.15302
12. Henry Echeverría, Andrea Jiménez, Suchismita Mishra, Daniel A. Quiroz, Mauricio Yépez, Odd Hadwiger number and graph products, arXiv:2603.28748 (2026), doi:10.48550/arXiv.2603.28748, https://arxiv.org/abs/2603.28748
13. Henry Echeverría, Jessica McDonald, Coloring graphs with independence number two and no odd clique immersions, arXiv:2605.04022 (2026), doi:10.48550/arXiv.2605.04022, https://arxiv.org/abs/2605.04022
14. Sergey Norin, Paul Seymour, Dense minors of graphs with independence number two, arXiv:2206.00186 (2022), doi:10.48550/arXiv.2206.00186, https://arxiv.org/abs/2206.00186
15. Jonathan C. Dahlke, The Abu-Khzam–Langston Conjecture for Graphs with α(G)=2, arXiv:2605.28159 (2026), doi:10.48550/arXiv.2605.28159, https://arxiv.org/abs/2605.28159
16. Rong Chen, Zijian Deng, Connected matching in graphs with independence number two, arXiv:2409.05920 (2024), doi:10.48550/arXiv.2409.05920, https://arxiv.org/abs/2409.05920