Hadwiger's conjecture for graphs with independence number at most two

Hadwiger's conjecture (1943) asserts that every graph$G$contains the complete graph$K_{\chi(G)}$as a minor, where$\chi(G)$is the chromatic number; it is proved only for$\chi(G)\le 6$and is open for every larger value. This record concerns its most celebrated structurally defined open case: graphs with independence number$\alpha(G)\le 2$(no three pairwise non-adjacent vertices), equivalently the complements of triangle-free graphs. Plummer, Stiebitz and Toft proved that Hadwiger's conjecture restricted to this class is equivalent to the statement that every$n$-vertex graph with$\alpha(G)\le 2$contains$K_{\lceil n/2\rceil}$as a minor. Seymour has singled this case out as likely decisive for the conjecture in general. The best general lower bound,$K_{\lceil n/3\rceil}$, dates to 1982; Norin and Seymour (2022) obtained an$\lceil n/2\rceil$-vertex minor missing only about 1.3% of all edges, and the biclique-minor conjectures of Woodall, Seymour and Botler et al. were proved for this class by Chen and Deng (2024) — but the clique minor$K_{\lceil n/2\rceil}$itself remains out of reach. A 2025 disproof of the odd Hadwiger conjecture, whose counterexamples have independence number two, refutes only the odd strengthening, not the ordinary conjecture. As of August 2026 the problem is open: it is not even known whether some constant$c>1/3$guarantees a$K_{\lceil cn\rceil}$minor in every such graph.

Background

All graphs here are finite and simple. A graph$H$is a minor of a graph$G$if$H$can be obtained from$G$by deleting vertices, deleting edges, and contracting edges (merging the two endpoints of an edge into a single vertex); equivalently,$G$contains$K_t$as a minor when$G$has$t$pairwise disjoint non-empty connected subgraphs (branch sets) every two of which are joined by at least one edge. The chromatic number$\chi(G)$is the least number of colours needed to colour the vertices so that adjacent vertices receive different colours. Hadwiger's conjecture (1943) asserts that every graph$G$contains$K_{\chi(G)}$as a minor. It generalises the Four Colour Theorem: it is known for$\chi(G)\le 6$, with the cases$\chi(G)=5$and$\chi(G)=6$depending on the Four Colour Theorem, and it remains open for every$\chi(G)\ge 7$. Let$\alpha(G)$denote the independence number, the maximum size of a set of pairwise non-adjacent vertices. This record concerns Hadwiger's conjecture for graphs with$\alpha(G)\le 2$— graphs containing no three pairwise non-adjacent vertices, i.e. exactly the complements of triangle-free graphs. The significance of this class was first pointed out by Duchet and Meyniel (1982) and, independently, Mader, and was highlighted in Seymour's survey: he writes that if Hadwiger's conjecture is true for graphs with stability number two then it is probably true in general, 'so it would be very nice to decide this case' (Costa–Luu–Wood–Yip 2025 quote this passage). Since every colour class is an independent set, an$n$-vertex graph with$\alpha(G)\le 2$satisfies$\chi(G)\ge\lceil n/2\rceil$, so Hadwiger's conjecture predicts at least a$K_{\lceil n/2\rceil}$minor; Plummer, Stiebitz and Toft (2003) proved that the conjecture restricted to this class is equivalent to the purely numerical statement that every$n$-vertex graph with$\alpha(G)\le 2$contains$K_{\lceil n/2\rceil}$as a minor. The known partial results delimit the gap sharply. A 1982 theorem of Duchet and Meyniel implies the lower bound$K_{\lceil n/3\rceil}$, as does the 'seagull packing' theorem of Chudnovsky and Seymour (2012), which in addition yields the full$K_{\lceil n/2\rceil}$minor whenever$G$contains a clique on at least$n/4$vertices. Norin and Seymour (2022) proved an approximate version: every$n$-vertex graph with$\alpha(G)\le 2$has a minor on exactly$\lceil n/2\rceil$vertices that is missing at most about 1.3% of all possible edges. Several variants are settled: Chen and Deng (2024) confirmed, for graphs with$\alpha(G)\le 2$, the 2001 conjecture of Woodall and Seymour that every graph$G$contains each complete bipartite graph$K_{\ell,\chi(G)-\ell}$on$\chi(G)$vertices as a minor (in the stronger form$K^{\ell}_{\ell,\chi(G)-\ell}$, where the side of size$\ell$is made a clique), also settling the 2023 conjecture of Botler et al.; the analogous bipartite immersion statements hold (Botler et al. 2024); conditional results exist for odd clique minors (Ji–Song–Weiss–Zhang 2025) and for the 'dominating' strengthening of Illingworth and Wood in which the branch sets must dominate the graph (Scully–Song 2025); and Hadwiger's conjecture itself has been verified for various hereditary subclasses (Li–Zhou; Costa–Luu–Wood–Yip 2025). None of these yields the clique minor$K_{\lceil n/2\rceil}$in general. A cautionary adjacent fact: the Odd Hadwiger conjecture — the strengthening demanding an odd$K_{\chi(G)}$minor, i.e. a minor model whose branch-set trees can be two-coloured so that tree edges are bichromatic while edges between trees are monochromatic — was disproved in 2025 by Kühn, Sauermann, Steiner and Wigderson, and their counterexamples are graphs with independence number two; this rules out odd-minor proof strategies for this class but has no direct implication for the ordinary conjecture, since an odd minor is always a minor but not conversely. As of August 2026, it is not even known whether some constant$c>1/3$guarantees a$K_{\lceil cn\rceil}$minor in every$n$-vertex graph with$\alpha(G)\le 2$(Bermúdez–Netto–Quiroz 2026).

Problem Statement

Prove or disprove: every graph$G$with independence number$\alpha(G)\le 2$contains the complete graph$K_{\chi(G)}$on$\chi(G)$vertices as a minor. By the theorem of Plummer, Stiebitz and Toft this is equivalent to the numerical form: every$n$-vertex graph$G$with$\alpha(G)\le 2$contains$K_{\lceil n/2\rceil}$as a minor, where the bound$\lceil n/2\rceil$is best possible in general (a disjoint union of two cliques on$\lfloor n/2\rfloor$and$\lceil n/2\rceil$vertices has$\alpha=2$and no larger clique minor). A graph with$\alpha(G)\le 2$and no$K_{\lceil n/2\rceil}$minor would satisfy$\chi(G)\ge\lceil n/2\rceil$, and would therefore also be a counterexample to Hadwiger's conjecture in general.

References

1. Hadwiger, Hugo. Über eine Klassifikation der Streckenkomplexe. Vierteljahresschrift der Naturforschenden Gesellschaft in Zürich 88 (1943), 133-142. Zbl 0061.41308, https://zbmath.org/?q=an:0061.41308
2. Duchet, P.; Meyniel, H. On Hadwiger's Number and the Stability Number. In: Graph Theory (Proceedings of the Conference on Graph Theory, Cambridge 1981), Annals of Discrete Mathematics 13 / North-Holland Mathematics Studies 62, North-Holland, 1982, pp. 71-73. DOI 10.1016/S0304-0208(08)73549-7, https://doi.org/10.1016/S0304-0208(08)73549-7
3. Plummer, M.; Stiebitz, M.; Toft, B. On a special case of Hadwiger's conjecture. Discussiones Mathematicae Graph Theory 23 (2003), 333-363. DOI 10.7151/dmgt.1206, https://doi.org/10.7151/dmgt.1206
4. Chudnovsky, M.; Seymour, P. Packing seagulls. Combinatorica 32 (2012), 251-282. DOI 10.1007/s00493-012-2594-2, https://doi.org/10.1007/s00493-012-2594-2
5. Seymour, P. Hadwiger's Conjecture. In: J. F. Nash Jr., M. Th. Rassias (eds.), Open Problems in Mathematics, Springer, 2016, 417-437. DOI 10.1007/978-3-319-32162-2_13, https://doi.org/10.1007/978-3-319-32162-2_13
6. Norin, Sergey; Seymour, Paul. Dense minors of graphs with independence number two. arXiv:2206.00186 (2022). DOI 10.48550/arXiv.2206.00186, https://arxiv.org/abs/2206.00186
7. Botler, Fábio; Jiménez, Andrea; Lintzmayer, Carla N.; Pastine, Adrián; Quiroz, Daniel A.; Sambinelli, Maycon. Biclique immersions in graphs with independence number 2. European Journal of Combinatorics 122 (2024), article 104042. DOI 10.1016/j.ejc.2024.104042, https://doi.org/10.1016/j.ejc.2024.104042 (preprint arXiv:2303.06483, https://arxiv.org/abs/2303.06483)
8. Li, Tong; Zhou, Qiang. Hadwiger's Conjecture for some graphs with independence number two. arXiv:2305.05868 (2023). DOI 10.48550/arXiv.2305.05868, https://arxiv.org/abs/2305.05868
9. Chen, Rong; Deng, Zijian. Seymour and Woodall's conjecture holds for graphs with independence number two. arXiv:2406.02643 (2024; v3 2025). DOI 10.48550/arxiv.2406.02643, https://arxiv.org/abs/2406.02643
10. Illingworth, Freddie; Wood, David R. Dominating $K_t$-Models. arXiv:2405.14299 (2024). DOI 10.48550/arXiv.2405.14299, https://arxiv.org/abs/2405.14299
11. Ji, Yuqing; Song, Zi-Xia; Weiss, Evan; Zhang, Xia. 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
12. Chen, Rong; Deng, Zijian. Odd complete bipartite minors in graphs with independence number two. arXiv:2505.03851 (2025). DOI 10.48550/arXiv.2505.03851, https://arxiv.org/abs/2505.03851
13. Scully, Michael; Song, Zi-Xia. Dominating Hadwiger's Conjecture for graphs $G$ with $\alpha(G)=2$. arXiv:2510.12564 (2025). DOI 10.48550/arXiv.2510.12564, https://arxiv.org/abs/2510.12564
14. Kühn, Marcus; Sauermann, Lisa; Steiner, Raphael; Wigderson, Yuval. Disproof of the Odd Hadwiger Conjecture. arXiv:2512.20392 (2025). DOI 10.48550/arXiv.2512.20392, https://arxiv.org/abs/2512.20392
15. Costa, Jofre; Luu, Eric; Wood, David R.; Yip, Jung Hon. Verifying Hadwiger's Conjecture for Examples of Graphs with $\alpha(G)=2$. arXiv:2512.17114 (2025). DOI 10.48550/arXiv.2512.17114, https://arxiv.org/abs/2512.17114
16. Bermúdez, Antonia; Netto, Bruno L.; Quiroz, Daniel A. 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