An Asymptotically Tight $t\log t$ Bound for $k$-Connected Subgraphs in Dense $K_t$-Minor-Free Graphs

Abstract

Delcourt and Postle reduced the Linear Hadwiger Conjecture to coloring $K_t$-minor-free graphs on $O(t\log^4 t)$ vertices. An important theorem in their proof process asserts that every sufficiently dense $K_t$-minor-free graph contains a small, highly connected subgraph. In this paper, we show that such a subgraph can be chosen to be smaller. More precisely, there exists an integer constant $C\geq 1$ such that, for all integers $t\geq 3$ and $k\geq t$, every $K_t$-minor-free graph $G$ with $d(G)\geq Ck$ contains a nonempty $k$-connected subgraph $H$ satisfying $v(H)\leq C^2t\log t$. Thus the structural bound improves from $O(t\log^3 t)$ to $O(t\log t)$. We also give a probabilistic construction showing that the $t\log t$ bound on $v(H)$ is best possible up to a constant factor. Consequently, the graphs occurring in the reduction have order $O(t\log^2 t)$ rather than $O(t\log^4 t)$.

Disclosure

“5 Acknowledgments This research was partially supported by the Natural Science Foundation of Fujian Province (Grant No. 2025J01486). Statement of AI Use. The central proof idea in this manuscript was developed with the assistance of GPT 5.6 Sol. The author subsequently refined the idea and wrote the manuscript, using the same model to assist with language polishing. References [1] B. Bollobás, P. A. Catlin and P. Erdős, Hadwiger’s conjecture is true for almost every g”

PDF page 10

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-23T19:02:53.960871Z

Structural counts