Large minors in graphs with given independence number

Research output: Contribution to journalArticlepeer-review


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>119.2.

Original languageEnglish (US)
Pages (from-to)2203-2215
Number of pages13
JournalDiscrete Mathematics
Issue number20
StatePublished - Oct 28 2011


  • Clique minor
  • Hadwiger's conjecture
  • Independence number

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Large minors in graphs with given independence number'. Together they form a unique fingerprint.

Cite this