2021/07/14 by Wales, Matthew
#05C83 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2107.06716
The Hadwiger number h(G) is the order of the largest complete minor in G. Does sufficient Hadwiger number imply a minor with additional properties? In [2], Geelen et al showed h(G)≥ (1+o(1))ct√(ln t) implies G has a bipartite subgraph with Hadwiger number at least t, for some explicit c∼ 1.276\dotsc. We improve this to h(G) ≥ (1+o(1))t√(log2 t), and provide a construction showing this is tight. We also derive improved bounds for the topological minor variant of this problem.