Complete Minors and Independence Number
Jacob Fox · SIAM Journal on Discrete Mathematics · 2010
Let G be a graph with n vertices and independence number $\alpha$. Hadwiger's conjecture implies that G contains a clique minor of order at least $n/\alpha$. In 1982, Duchet and Meyniel proved that this bound holds within a factor 2. Our main result gives the first improvement on their bound by an absolute constant factor. We show that G contains a clique minor of order larger than $.504n/\alpha$. We also prove related results giving lower bounds on the order of the largest clique minor.