Article ID Journal Published Year Pages File Type
6423598 Discrete Mathematics 2011 13 Pages PDF
Abstract

A weakening of Hadwiger's conjecture states that every n-vertex graph with independence number α has a clique minor of size at least nα. Extending ideas of Fox (2010) [6], we prove that such a graph has a clique minor with at least n(2−c)α vertices where c>1/19.2.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,