DMGT

Discussiones Mathematicae Graph Theory 31(4) (2011) 639-674
DOI: https://doi.org/10.7151/dmgt.1571

Complete Minors, Independent Sets, and Chordal Graphs

József Balogh

Department of Mathematics
University of Illinois
Urbana, IL 61801, USA
Department of Mathematics
University of California, San Diego
La Jolla, CA 92093, USA

John Lenz, Hehui Wu

Department of Mathematics
University of Illinois
Urbana, IL 61801, USA

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: clique minor, independence number, Hadwiger conjecture, chordal graphs

2010 Mathematics Subject Classification: Primary: 05C83,
Secondary: 05C69, 05C70.

References

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

Received 14 September 2009
Revised 15 September 2010
Accepted 6 October 2010