Complete minors, independent sets, and chordal graphs

József Balogh, John Lenz, Hehui Wu

Research output: Contribution to journalArticlepeer-review

Abstract

The Hadwiger number h(G) of a graph G is the maximum size of a complete minor of G. Hadwiger's Conjecture states that h(G) ≥ Χ(G). Since Χ(G)α(G) ≥ |V (G)|, Hadwiger's Conjecture implies that α(G)h(G) ≥ |V (G)|. We show that (2α(G)[logτ (τα(G)/2)])h(G) ≥ |V (G)| where τ ∼ 6.83. For graphs with α(G) ≥ 14, this improves on a recent result of Kawarabayashi and Song who showed (2α(G) - 2) h(G) ≥ |V (G)| when α(G) ≥ 3.

Original languageEnglish (US)
Pages (from-to)639-674
Number of pages36
JournalDiscussiones Mathematicae - Graph Theory
Volume31
Issue number4
DOIs
StatePublished - 2011

Keywords

  • Chordal graphs
  • Clique minor
  • Hadwiger conjecture
  • Independence number

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Complete minors, independent sets, and chordal graphs'. Together they form a unique fingerprint.

Cite this