Complete minors, independent sets, and chordal graphs

József Balogh; John Lenz; Hehui Wu

doi:10.7151/dmgt.1571

Complete minors, independent sets, and chordal graphs

József Balogh, John Lenz, Hehui Wu

Mathematics

Research output: Contribution to journal › Article › peer-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 language	English (US)
Pages (from-to)	639-674
Number of pages	36
Journal	Discussiones Mathematicae - Graph Theory
Volume	31
Issue number	4
DOIs	https://doi.org/10.7151/dmgt.1571
State	Published - 2011

Keywords

Chordal graphs
Clique minor
Hadwiger conjecture
Independence number

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Online availability

10.7151/dmgt.1571

Library availability

Discover UIUC Full Text

Cite this

@article{1f963a3773cd4f1e875d42ab8721d761,

title = "Complete minors, independent sets, and chordal graphs",

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.",

keywords = "Chordal graphs, Clique minor, Hadwiger conjecture, Independence number",

author = "J{\'o}zsef Balogh and John Lenz and Hehui Wu",

year = "2011",

doi = "10.7151/dmgt.1571",

language = "English (US)",

volume = "31",

pages = "639--674",

journal = "Discussiones Mathematicae - Graph Theory",

issn = "1234-3099",

publisher = "University of Zielona Gora",

number = "4",

}

TY - JOUR

T1 - Complete minors, independent sets, and chordal graphs

AU - Balogh, József

AU - Lenz, John

AU - Wu, Hehui

PY - 2011

Y1 - 2011

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

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

KW - Chordal graphs

KW - Clique minor

KW - Hadwiger conjecture

KW - Independence number

UR - http://www.scopus.com/inward/record.url?scp=80054072285&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80054072285&partnerID=8YFLogxK

U2 - 10.7151/dmgt.1571

DO - 10.7151/dmgt.1571

M3 - Article

AN - SCOPUS:80054072285

SN - 1234-3099

VL - 31

SP - 639

EP - 674

JO - Discussiones Mathematicae - Graph Theory

JF - Discussiones Mathematicae - Graph Theory

IS - 4

ER -

Complete minors, independent sets, and chordal graphs

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this