An O(tlog t) Bound for k-Connected Subgraphs in Dense K_t-Minor-Free Graphs

2026/07/23 by Xinheng Lin
#math.CO

paper · pdf

Abstract

Delcourt and Postle reduced the Linear Hadwiger Conjecture to coloring K_t-minor-free graphs on O(tlog⁴ t) vertices. A key ingredient in their proof 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≥ 1 such that, for all integers t≥ 3 and k≥ t, every K_t-minor-free graph G with d(G)≥ Ck contains a nonempty k-connected subgraph H satisfying v(H)≤ C²tlog t. Thus the structural bound improves from O(tlog³ t) to O(tlog t), and the graphs occurring in the reduction have order O(tlog² t) rather than O(tlog⁴ t).

Related

• Reducing Linear Hadwiger's Conjecture to Coloring Small Graphs
• Improved bound for Hadwiger's conjecture
• Asymptotic Equivalence of Hadwiger's Conjecture and its Odd Minor-Variant
• Improved bound for improper colorings of graphs with no odd clique minor
• Connectivity and choosability of graphs with no K_t minor