Geodesic
Complete minors, independent sets, and chordal graphs
Discussiones Mathematicae. Graph Theory, Tome 31 (2011) no. 4, pp. 639-674

Voir la notice de l'article provenant de la source Library of Science

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: clique minor, independence number, Hadwiger conjecture, chordal graphs 
@article{DMGT_2011_31_4_a2,
     author = {Balogh, J\'ozsef and Lenz, John and Wu, Hehui},
     title = {Complete minors, independent sets, and chordal graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {639--674},
     publisher = {mathdoc},
     volume = {31},
     number = {4},
     year = {2011},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2011_31_4_a2/}
}
TY  - JOUR
AU  - Balogh, József
AU  - Lenz, John
AU  - Wu, Hehui
TI  - Complete minors, independent sets, and chordal graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2011
SP  - 639
EP  - 674
VL  - 31
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2011_31_4_a2/
LA  - en
ID  - DMGT_2011_31_4_a2
ER  - 
%0 Journal Article
%A Balogh, József
%A Lenz, John
%A Wu, Hehui
%T Complete minors, independent sets, and chordal graphs
%J Discussiones Mathematicae. Graph Theory
%D 2011
%P 639-674
%V 31
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2011_31_4_a2/
%G en
%F DMGT_2011_31_4_a2
Balogh, József; Lenz, John; Wu, Hehui. Complete minors, independent sets, and chordal graphs. Discussiones Mathematicae. Graph Theory, Tome 31 (2011) no. 4, pp. 639-674. http://geodesic.mathdoc.fr/item/DMGT_2011_31_4_a2/