The Rolek–Song edge-density conjecture: at $(t-2)n-\binom{t-1}{2}+1$ edges every graph has a $K_t$ minor or is $(t-1)$-colorable

Hadwiger's conjecture (1943) asserts that every graph with no $K_t$ minor is $(t-1)$-colorable; it is proved for $t \le 6$ and open for every $t \ge 7$. Rolek and Song (2017; restated as Conjecture 1.1 of Rolek's 2020 paper 'Graphs with no $K_9^=$ minor are 10-colorable') posed an edge-density weakening of Hadwiger's conjecture: every graph on $n$ vertices with at least $(t-2)n-\binom{t-1}{2}+1$ edges either has a $K_t$ minor or is $(t-1)$-colorable. The threshold is Mader's extremal bound for forcing a $K_t$ minor: the join of $K_{t-2}$ with an independent set on $n-t+2$ vertices has $(t-2)n-\binom{t-1}{2}$ edges, chromatic number $t-1$, and no $K_t$ minor, so at the un-incremented bound the minor conclusion alone already fails while the disjunctive conclusion still holds for this example. The conjecture holds for $t \le 9$ by the exact extremal theorems of Dirac and Mader ($t \le 7$), Jørgensen ($t=8$), and Song and Thomas ($t=9$). The open core is $t \ge 10$; the first open case is $t=10$, where at least $8n-35$ edges should force a $K_{10}$ minor or 9-colorability. Rolek and Song proved that the conjecture implies every $K_t$-minor-free graph is $(2t-6)$-colorable for all $t \ge 5$ — a linear bound in Hadwiger's conjecture with explicit constant 2, still far beyond the best known $O(t\log\log t)$. No resolution for any $t \ge 10$ and no counterexample is known in the literature through 2026; any counterexample would itself refute Hadwiger's conjecture.

Background

A graph $H$ is a minor of a graph $G$ if $H$ can be obtained from $G$ by a sequence of vertex deletions, edge deletions, and edge contractions, where contracting an edge means identifying its two endpoints into a single vertex. The chromatic number $\chi(G)$ is the least number of colors needed to color the vertices of $G$ so that adjacent vertices receive different colors. Hadwiger's conjecture (1943) asserts that for every integer $t \ge 1$, every graph with no $K_t$ minor is $(t-1)$-colorable, where $K_t$ denotes the complete graph on $t$ vertices; equivalently, every graph with chromatic number at least $t$ contains a $K_t$ minor. The cases $t \le 3$ are easy, the case $t = 4$ was proved by Hadwiger and Dirac, the case $t=5$ is equivalent to the Four Color Theorem (Wagner 1937), and the case $t=6$ was settled by Robertson, Seymour, and Thomas (1993); for every $t \ge 7$ it remains open and is considered one of the deepest problems in graph theory.

Because Hadwiger's conjecture is out of reach, Rolek and Song (2017) proposed an edge-density weakening whose threshold is Mader's extremal bound for forcing a $K_t$ minor. The graph obtained from $K_{t-2}$ by joining it to an independent set of $n-t+2$ vertices (every vertex of the $K_{t-2}$ adjacent to every vertex of the independent set) has exactly $(t-2)n-\binom{t-1}{2}$ edges, chromatic number $t-1$, and no $K_t$ minor: a family of $t$ pairwise-adjacent branch sets (connected vertex sets representing the vertices of a $K_t$ minor) can have at most $t-2$ members meeting the clique, so at most $t-1$ members in all. Dirac (for $p \le 5$) and Mader (for $p = 6, 7$) proved that one more edge already forces the minor outright: every graph on $n \ge p$ vertices with at least $(p-2)n-\binom{p-1}{2}+1$ edges has a $K_p$ minor. Jørgensen (1994) and Song and Thomas (2006) extended this to $p = 8$ and $p = 9$ up to explicitly described exceptions — cockades, graphs built recursively by gluing copies of fixed building blocks along cliques of a prescribed size, together with one sporadic graph at $p = 9$ — and every exceptional graph there is $(p-1)$-colorable. Rolek and Song therefore posed the conjecture below (Conjecture 5.1 of their paper, restated as Conjecture 1.1 of Rolek's 2020 paper on graphs with no $K_9^=$ minor, where $K_t^=$ denotes $K_t$ with two edges deleted), observing that it holds for all $t \le 9$.

For large $t$ the naive pure-extremal extension is false: Kostochka and Thomason determined that the extremal average degree forcing a $K_t$ minor is of order $t\sqrt{\log t}$ — average degree $O(t\sqrt{\log t})$ forces a $K_t$ minor, and graphs with average degree of the same order and no $K_t$ minor exist — so for large $t$ there are $K_t$-minor-free graphs with more than $(t-2)n$ edges. The disjunctive conclusion '$(t-1)$-colorable' is what can still hold for every $t$: a graph violating the conjecture would be a graph with no $K_t$ minor that is not $(t-1)$-colorable, that is, a counterexample to Hadwiger's conjecture itself.

The conjecture matters because Rolek and Song proved (Theorem 5.2 of their paper) that it implies every graph with no $K_t$ minor is $(2t-6)$-colorable for all $t \ge 5$. This would settle the 'linear Hadwiger' target — the assertion that $K_t$-minor-free graphs have chromatic number at most a constant times $t$ — with explicit constant 2. Unconditionally, the best bounds on the chromatic number of $K_t$-minor-free graphs went from Kostochka and Thomason's $O(t\sqrt{\log t})$ to the first order-of-magnitude improvement by Norin, Postle, and Song (2023), then to $O(t\log\log t)$ by Delcourt and Postle (2025), who also reduced linear Hadwiger to coloring small such graphs; Wang (2025) obtained $O(t(\log\log t)^5)$ in a related line. None of these bounds is linear.

Problem Statement

For every integer $t \ge 1$, prove or refute: every graph $G$ on $n$ vertices with at least

$$|E(G)| \ge (t-2)n-\binom{t-1}{2}+1$$

edges either contains $K_t$ as a minor or satisfies $\chi(G) \le t-1$.

The cases $t \le 9$ are already theorems: for $t \le 7$ the edge bound alone forces a $K_t$ minor (Dirac, Mader), and for $t = 8, 9$ the only graphs at the bound without a $K_t$ minor are the $(t-1)$-colorable cockade exceptions of Jørgensen and Song–Thomas, together with one sporadic graph ($K_{2,2,2,3,3}$, which is 5-colorable) at $t = 9$. The problem is therefore to settle the conjecture on the remaining range $t \ge 10$: either prove it for all $t \ge 10$, or refute it by exhibiting, for some $t \ge 10$, a graph $G$ on $n$ vertices with at least $(t-2)n-\binom{t-1}{2}+1$ edges, no $K_t$ minor, and chromatic number at least $t$. The first open case is $t = 10$: every graph on $n$ vertices with at least $8n-35$ edges has a $K_{10}$ minor or is 9-colorable. The role of the '$+1$' is that the minor alternative alone fails at the un-incremented bound: the join of $K_{t-2}$ with an independent set on $n-t+2$ vertices has $(t-2)n-\binom{t-1}{2}$ edges and no $K_t$ minor; since it is $(t-1)$-colorable, it satisfies the disjunctive conclusion and so is not a counterexample to the conjecture.

References

1. K. Wagner, Über eine Eigenschaft der ebenen Komplexe, Mathematische Annalen 114 (1937) 570–590, DOI 10.1007/BF01594196, https://doi.org/10.1007/BF01594196
2. H. Hadwiger, Über eine Klassifikation der Streckenkomplexe, Vierteljahresschrift der Naturforschenden Gesellschaft in Zürich 88 (1943) 133–142, zbMATH 3102312, https://zbmath.org/3102312
3. G. A. Dirac, Homomorphism theorems for graphs, Mathematische Annalen 153 (1964) 69–80, DOI 10.1007/BF01361708, https://doi.org/10.1007/BF01361708
4. W. Mader, Homomorphiesätze für Graphen, Mathematische Annalen 178 (1968) 154–168, DOI 10.1007/BF01350657, https://doi.org/10.1007/BF01350657
5. A. V. Kostochka, On the minimum of the Hadwiger number for graphs with a given mean degree of vertices, Metody Diskretnogo Analiza 38 (1982) 37–58; English translation in American Mathematical Society Translations, Series 2, 132 (1986) 15–31, DOI 10.1090/trans2/132/03, https://doi.org/10.1090/trans2/132/03
6. N. Robertson, P. Seymour, R. Thomas, Hadwiger's conjecture for $K_6$-free graphs, Combinatorica 13 (1993) 279–361, DOI 10.1007/BF01202354, https://doi.org/10.1007/BF01202354
7. L. K. Jørgensen, Contractions to $K_8$, Journal of Graph Theory 18 (1994) 431–448, DOI 10.1002/jgt.3190180502, https://doi.org/10.1002/jgt.3190180502
8. A. Thomason, The extremal function for complete minors, Journal of Combinatorial Theory, Series B 81 (2001) 318–338, DOI 10.1006/jctb.2000.2013, https://doi.org/10.1006/jctb.2000.2013
9. Z.-X. Song, R. Thomas, The extremal function for $K_9$ minors, Journal of Combinatorial Theory, Series B 96 (2006) 240–252, DOI 10.1016/j.jctb.2005.07.008, https://doi.org/10.1016/j.jctb.2005.07.008
10. M. Rolek, Z.-X. Song, Coloring graphs with forbidden minors, Journal of Combinatorial Theory, Series B 127 (2017) 14–31, DOI 10.1016/j.jctb.2017.05.001, arXiv:1606.05507, https://arxiv.org/abs/1606.05507
11. M. Rolek, Graphs with no $K_9^=$ minor are 10-colorable, Journal of Graph Theory 93 (2020) 560–565, DOI 10.1002/jgt.22502, arXiv:1809.05975, https://arxiv.org/abs/1809.05975
12. M. Rolek, The extremal function for $K_9^=$ minors, Journal of Graph Theory 94 (2020) 206–223, DOI 10.1002/jgt.22515, https://doi.org/10.1002/jgt.22515
13. M. Lafferty, Z.-X. Song, Every graph with no $\mathcal{K}_9^{-6}$ minor is 8-colorable, arXiv:2209.05259 (2022), https://arxiv.org/abs/2209.05259
14. M. Rolek, Z.-X. Song, R. Thomas, Properties of 8-contraction-critical graphs with no $K_7$ minor, European Journal of Combinatorics 110 (2023) 103711, DOI 10.1016/j.ejc.2023.103711, https://doi.org/10.1016/j.ejc.2023.103711
15. S. Norin, L. Postle, Z.-X. Song, Breaking the degeneracy barrier for coloring graphs with no $K_t$ minor, Advances in Mathematics 422 (2023) 109020, DOI 10.1016/j.aim.2023.109020, arXiv:1910.09378, https://arxiv.org/abs/1910.09378
16. M. Delcourt, L. 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
17. Y. Wang, Improved bound for Hadwiger's conjecture, Graphs and Combinatorics 41 (2025), Paper No. 36, DOI 10.1007/s00373-025-02899-5, arXiv:2108.09230, https://arxiv.org/abs/2108.09230
18. S. Norin, A. Totschnig, Every graph with no $K_7^{\vee}$-minor is 6-colorable, arXiv:2507.03244 (2025), https://arxiv.org/abs/2507.03244
19. M. Lafferty, R. Liu, M. Rolek, G. Yu, Connectivity of contraction-critical graphs, arXiv:2509.07144 (2025), https://arxiv.org/abs/2509.07144
20. S. Norin, P. Seymour, Dense minors of graphs with independence number two, Journal of Combinatorial Theory, Series B 176 (2026) 101–110, DOI 10.1016/j.jctb.2025.08.005, arXiv:2206.00186, https://arxiv.org/abs/2206.00186