Forcing a $K_t$ minor from polylogarithmically many disjoint $Ct$-connected subgraphs at linear connectivity (Question 6.1 of Norin–Postle–Song)

Norin, Postle and Song proved that every graph with no $K_t$ minor is $O(t(\log t)^{\beta})$-colorable for every $\beta>1/4$, the first asymptotic improvement of the Kostochka–Thomason $O(t\sqrt{\log t})$ bound. The engine of their proof is a linking theorem: a graph of connectivity at least $Ct(\log t)^{1/4}$ containing at least $\sqrt{\log t}/2$ vertex-disjoint subgraphs of density at least $Ct(\log t)^{1/4}$ has a $K_t$ minor. Their Question 6.1 asks whether the logarithmic connectivity overhead can be eliminated: does there exist an absolute constant $C>0$ such that, for every integer $t\ge 1$, every graph of connectivity at least $Ct$ containing at least $(\log t)^C$ vertex-disjoint subgraphs of connectivity at least $Ct$ has a $K_t$ minor? The question remains open. The published successor work of Delcourt and Postle improved the chromatic-number bound to $O(t\log\log t)$ by a different route — sequential, recursive minor constructions and a reduction to coloring small graphs (after Postle's announced density-increment improvements were withdrawn and merged into that paper) — and the linear-connectivity regime probed by Question 6.1 is explicitly identified in the literature as the central obstacle for connectivity-based methods, while known constructions of $K_t$-minor-free graphs at linear connectivity are exponentially far from refuting the question.

Background

A graph $H$ is a minor of a graph $G$ if $H$ can be obtained from a subgraph of $G$ by contracting edges; equivalently, each vertex of $H$ corresponds to a connected branch set of $G$, and the branch sets are pairwise disjoint. 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 every graph with no $K_t$ minor — no complete graph on $t$ vertices as a minor — is $(t-1)$-colorable; it is known for $t\le 6$ and open for all $t\ge 7$. The vertex connectivity $\kappa(G)$ is the minimum number of vertices whose deletion disconnects $G$ or reduces it to a single vertex (with $\kappa(K_n)=n-1$), and is never larger than the minimum degree; the density $d(G)$ of a non-null graph is its edge-to-vertex ratio, which controls its average degree.

Kostochka (1984) and Thomason (1984) independently proved that every graph with no $K_t$ minor has average degree $O(t\sqrt{\log t})$, and random graphs show this is tight, so any argument based only on degeneracy (hereditarily small average degree) is capped at $O(t\sqrt{\log t})$ colors — the degeneracy barrier. The Linear Hadwiger Conjecture predicts that $\chi(G)=O(t)$ for graphs with no $K_t$ minor. Norin, Postle and Song made the first asymptotic improvement over the barrier: every graph with no $K_t$ minor is $O(t(\log t)^{\beta})$-colorable for every $\beta>1/4$. Their strategy, applied to a minimum counterexample, is to find many pairwise vertex-disjoint dense subgraphs ("pieces") and to link them, all at once, into a single $K_t$ minor. The linking step is their Theorem 2.6: there is a constant $C$ such that every graph $G$ with $\kappa(G)\ge Ct(\log t)^{1/4}$ containing $r\ge\sqrt{\log t}/2$ pairwise vertex-disjoint subgraphs $H_1,\dots,H_r$ with $d(H_i)\ge Ct(\log t)^{1/4}$ for all $i$ has a $K_t$ minor; its proof adapts an extremal argument of Thomason (2001). As Norin's ICM survey explains, the $(\log t)^{1/4}$ factor arises structurally from splitting $K_t$ into roughly $\sqrt{\log t}$ pieces that the linkage machinery must join, and it is the bottleneck of the whole approach.

At purely linear connectivity the only general forcing result is due to Böhme, Kawarabayashi, Maharry and Mohar: for every $t$ there exists $N(t)$ such that every graph with $\kappa(G)\ge 31(t+1)/2$ and at least $N(t)$ vertices has a $K_t$ minor. However $N(t)$ comes from the Robertson–Seymour graph-minor structure theory and has no reasonable explicit bound. Since every $Ct$-connected graph has at least $Ct+1$ vertices, $r\ge N(t)$ vertex-disjoint $Ct$-connected pieces force $v(G)\ge N(t)$, so the variant of Question 6.1 with $r\ge N(t)$ is trivially positive; the substantive question is whether polylogarithmically many pieces suffice.

Problem Statement

Does there exist an absolute constant $C>0$ such that the following holds for every integer $t\ge 1$: if $G$ is a graph and $H_1,H_2,\dots,H_r$ are pairwise vertex-disjoint subgraphs of $G$ such that $r\ge(\log t)^C$, $\kappa(G)\ge Ct$, and $\kappa(H_i)\ge Ct$ for every $i\in\{1,\dots,r\}$, then $G$ has a $K_t$ minor? Here $K_t$ denotes the complete graph on $t$ vertices, a minor of $G$ being a graph obtainable from a subgraph of $G$ by contracting edges, and $\kappa(\cdot)$ denotes vertex connectivity, the minimum number of vertices whose deletion disconnects the graph or reduces it to a single vertex. The constant $C$ must be absolute — independent of $t$ and of the graphs. This is Question 6.1 of Norin–Postle–Song, posed to determine the limits of their linking-based approach to coloring $K_t$-minor-free graphs: a positive answer would show that the $(\log t)^{1/4}$ connectivity overhead of their Theorem 2.6 can be removed at the price of allowing $(\log t)^C$ pieces, while a negative answer would expose an inherent barrier to purely connectivity-based linking toward linear-in-$t$ colorability.

References

1. Sergey Norin, Luke Postle, Zi-Xia 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, https://arxiv.org/abs/1910.09378
2. 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://arxiv.org/abs/2108.01633
3. Luke Postle, Further progress towards Hadwiger's conjecture, arXiv:2006.11798 (2020; withdrawn by the author in May 2022 and merged into arXiv:2108.01633), https://arxiv.org/abs/2006.11798
4. Sergey Norin, Luke Postle, Connectivity and choosability of graphs with no $K_t$ minor, Journal of Combinatorial Theory, Series B 158 (2023) 283–300, doi:10.1016/j.jctb.2021.02.001, https://arxiv.org/abs/2004.10367
5. Xinheng Lin, An asymptotically tight $t\log t$ bound for $k$-connected subgraphs in dense $K_t$-minor-free graphs, preprint (2026), arXiv:2607.21222, https://arxiv.org/abs/2607.21222
6. Thomas Böhme, Ken-ichi Kawarabayashi, John Maharry, Bojan Mohar, Linear connectivity forces large complete bipartite minors, Journal of Combinatorial Theory, Series B 99 (2009) 557–582, doi:10.1016/j.jctb.2008.07.006, https://doi.org/10.1016/j.jctb.2008.07.006
7. A. V. Kostochka, Lower bound of the Hadwiger number of graphs by their average degree, Combinatorica 4 (1984) 307–316, doi:10.1007/BF02579141, https://doi.org/10.1007/BF02579141
8. Andrew Thomason, An extremal function for contractions of graphs, Mathematical Proceedings of the Cambridge Philosophical Society 95 (1984) 261–265, doi:10.1017/S0305004100061521, https://doi.org/10.1017/S0305004100061521
9. Andrew 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
10. Sergey Norin, Recent progress towards Hadwiger's conjecture, Proceedings of the International Congress of Mathematicians (ICM 2022), EMS Press, 2023, pp. 4606–4620, doi:10.4171/icm2022/102, https://doi.org/10.4171/icm2022/102
11. Hugo Hadwiger, Über eine Klassifikation der Streckenkomplexe, Vierteljahrsschrift der naturforschenden Gesellschaft in Zürich 88 (1943) 133–142, Zbl 0061.41308, https://zbmath.org/?q=an%3A3102312