Complete minors, independent sets, and chordal graphs

József Balogh; John Lenz; Hehui Wu

Discussiones Mathematicae Graph Theory (2011)

  • Volume: 31, Issue: 4, page 639-674
  • ISSN: 2083-5892

Abstract

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

How to cite

top

József Balogh, John Lenz, and Hehui Wu. "Complete minors, independent sets, and chordal graphs." Discussiones Mathematicae Graph Theory 31.4 (2011): 639-674. <http://eudml.org/doc/270983>.

@article{JózsefBalogh2011,
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.},
author = {József Balogh, John Lenz, Hehui Wu},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {clique minor; independence number; Hadwiger conjecture; chordal graphs},
language = {eng},
number = {4},
pages = {639-674},
title = {Complete minors, independent sets, and chordal graphs},
url = {http://eudml.org/doc/270983},
volume = {31},
year = {2011},
}

TY - JOUR
AU - József Balogh
AU - John Lenz
AU - Hehui Wu
TI - Complete minors, independent sets, and chordal graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2011
VL - 31
IS - 4
SP - 639
EP - 674
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.
LA - eng
KW - clique minor; independence number; Hadwiger conjecture; chordal graphs
UR - http://eudml.org/doc/270983
ER -

References

top
  1. [1] K. Appel and W. Haken, Every planar map is four colorable. I. Discharging, Illinois J. Math. 21 (1977) 429-490. Zbl0387.05009
  2. [2] K. Appel, W. Haken and J. Koch, Every planar map is four colorable. II. Reducibility, Illinois J. Math. 21 (1977) 491-567. Zbl0387.05010
  3. [3] J. Balogh, J. Lenz and H. Wu, Complete Minors, Independent Sets, and Chordal Graphs, http://arxiv.org/abs/0907.2421. Zbl1255.05184
  4. [4] C. Berge, Les problemes de coloration en theorie des graphes, Publ. Inst. Statist. Univ. Paris 9 (1960) 123-160. Zbl0103.16201
  5. [5] M. Chudnovsky and A. Fradkin, An approximate version of Hadwiger's conjecture for claw-free graphs, J. Graph Theory 63 (2010) 259-278. Zbl1216.05061
  6. [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. Zbl0046.41001
  7. [7] G. Dirac, On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg 25 (1961) 71-76, doi: 10.1007/BF02992776. Zbl0098.14703
  8. [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. Zbl0522.05060
  9. [9] J. Fox, Complete minors and independence number, to appear in SIAM J. Discrete Math. Zbl1221.05289
  10. [10] H. Hadwiger, Uber eine Klassifikation der Streckenkomplexe, Vierteljschr. Naturforsch. Ges. Zürich 88 (1943) 133-142. Zbl0061.41308
  11. [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. Zbl1080.05074
  12. [12] K. Kawarabayashi and Z. Song, Independence number and clique minors, J. Graph Theory 56 (2007) 219-226, doi: 10.1002/jgt.20268. Zbl1135.05068
  13. [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. Zbl0239.05111
  14. [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. Zbl0628.05052
  15. [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. Zbl1053.05052
  16. [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. Zbl0883.05056
  17. [17] N. Robertson, P. Seymour and R. Thomas, Hadwiger's conjecture for K₆-free graphs, Combinatorica 13 (1993) 279-361, doi: 10.1007/BF01202354. Zbl0830.05028
  18. [18] B. Toft, A survey of Hadwiger's conjecture, Congr. Numer. 115 (1996) 249-283, Surveys in Graph Theory (San Francisco, CA, 1995). Zbl0895.05025
  19. [19] K. Wagner, Uber eine Eigenschaft der ebenen Komplexe, Math. Ann. 114 (1937) 570-590, doi: 10.1007/BF01594196. Zbl63.0550.01
  20. [20] D. Wood, Independent sets in graphs with an excluded clique minor, Discrete Math. Theor. Comput. Sci. 9 (2007) 171-175. Zbl1153.05049
  21. [21] D.R. Woodall, Subcontraction-equivalence and Hadwiger's conjecture, J. Graph Theory 11 (1987) 197-204, doi: 10.1002/jgt.3190110210. Zbl0672.05027

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.