COMPLETE MINORS AND INDEPENDENCE NUMBER

摘要

Let G be a graph with n vertices and independence number α. Hadwiger's conjecture implies that G contains a clique minor of order at least n/α. 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/α. We also prove related results giving lower bounds on the order of the largest clique minor.