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/

[1] K. Appel and W. Haken, Every planar map is four colorable. I. Discharging, Illinois J. Math. 21 (1977) 429-490.

[2] K. Appel, W. Haken and J. Koch, Every planar map is four colorable. II. Reducibility, Illinois J. Math. 21 (1977) 491-567.

[3] J. Balogh, J. Lenz and H. Wu, Complete Minors, Independent Sets, and Chordal Graphs, http://arxiv.org/abs/0907.2421.

[4] C. Berge, Les problemes de coloration en theorie des graphes, Publ. Inst. Statist. Univ. Paris 9 (1960) 123-160.

[5] M. Chudnovsky and A. Fradkin, An approximate version of Hadwiger's conjecture for claw-free graphs, J. Graph Theory 63 (2010) 259-278.

[6] G. Dirac, A property of 4-chromatic graphs and some remarks on critical graphs, J. London Math. Soc. 27 (1952) 85-92, doi: 10.1112/jlms/s1-27.1.85.

[7] G. Dirac, On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg 25 (1961) 71-76, doi: 10.1007/BF02992776.

[8] P. Duchet and H. Meyniel, On Hadwiger's number and the stability number, in: Graph Theory (Cambridge, 1981), (North-Holland, Amsterdam, 1982) 71-73.

[9] J. Fox, Complete minors and independence number, to appear in SIAM J. Discrete Math.

[10] H. Hadwiger, Uber eine Klassifikation der Streckenkomplexe, Vierteljschr. Naturforsch. Ges. Zürich 88 (1943) 133-142.

[11] K. Kawarabayashi, M. Plummer and B. Toft, Improvements of the theorem of Duchet and Meyniel on Hadwiger's conjecture, J. Combin. Theory (B) 95 (2005) 152-167, doi: 10.1016/j.jctb.2005.04.001.

[12] K. Kawarabayashi and Z. Song, Independence number and clique minors, J. Graph Theory 56 (2007) 219-226, doi: 10.1002/jgt.20268.

[13] L. Lovász, Normal hypergraphs and the perfect graph conjecture, Discrete Math. 2 (1972) 253-267, doi: 10.1016/0012-365X(72)90006-4.

[14] F. Maffray and H. Meyniel, On a relationship between Hadwiger and stability numbers, Discrete Math. 64 (1987) 39-42, doi: 10.1016/0012-365X(87)90238-X.

[15] M. Plummer, M. Stiebitz and B. Toft, On a special case of Hadwiger's conjecture, Discuss. Math. Graph Theory 23 (2003) 333-363, doi: 10.7151/dmgt.1206.

[16] N. Robertson, D. Sanders, P. Seymour and R. Thomas, The four-colour theorem, J. Combin. Theory (B) 70 (1997) 2-44, doi: 10.1006/jctb.1997.1750.

[17] N. Robertson, P. Seymour and R. Thomas, Hadwiger's conjecture for K₆-free graphs, Combinatorica 13 (1993) 279-361, doi: 10.1007/BF01202354.

[18] B. Toft, A survey of Hadwiger's conjecture, Congr. Numer. 115 (1996) 249-283, Surveys in Graph Theory (San Francisco, CA, 1995).

[19] K. Wagner, Uber eine Eigenschaft der ebenen Komplexe, Math. Ann. 114 (1937) 570-590, doi: 10.1007/BF01594196.

[20] D. Wood, Independent sets in graphs with an excluded clique minor, Discrete Math. Theor. Comput. Sci. 9 (2007) 171-175.

[21] D.R. Woodall, Subcontraction-equivalence and Hadwiger's conjecture, J. Graph Theory 11 (1987) 197-204, doi: 10.1002/jgt.3190110210.