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 language | English (US) |
---|---|
Pages (from-to) | 639-674 |
Number of pages | 36 |
Journal | Discussiones Mathematicae - Graph Theory |
Volume | 31 |
Issue number | 4 |
DOIs | |
State | Published - 2011 |
Keywords
- Chordal graphs
- Clique minor
- Hadwiger conjecture
- Independence number
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics