On a special case of Hadwiger's conjecture

Michael D. Plummer; Michael Stiebitz; Bjarne Toft

Discussiones Mathematicae Graph Theory (2003)

  • Volume: 23, Issue: 2, page 333-363
  • ISSN: 2083-5892

Abstract

top
Hadwiger's Conjecture seems difficult to attack, even in the very special case of graphs G of independence number α(G) = 2. We present some results in this special case.

How to cite

top

Michael D. Plummer, Michael Stiebitz, and Bjarne Toft. "On a special case of Hadwiger's conjecture." Discussiones Mathematicae Graph Theory 23.2 (2003): 333-363. <http://eudml.org/doc/270755>.

@article{MichaelD2003,
abstract = {Hadwiger's Conjecture seems difficult to attack, even in the very special case of graphs G of independence number α(G) = 2. We present some results in this special case.},
author = {Michael D. Plummer, Michael Stiebitz, Bjarne Toft},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {Hadwiger's Conjecture; complete minor; independence number; connected matching; Hadwiger's conjecture; -critical graph},
language = {eng},
number = {2},
pages = {333-363},
title = {On a special case of Hadwiger's conjecture},
url = {http://eudml.org/doc/270755},
volume = {23},
year = {2003},
}

TY - JOUR
AU - Michael D. Plummer
AU - Michael Stiebitz
AU - Bjarne Toft
TI - On a special case of Hadwiger's conjecture
JO - Discussiones Mathematicae Graph Theory
PY - 2003
VL - 23
IS - 2
SP - 333
EP - 363
AB - Hadwiger's Conjecture seems difficult to attack, even in the very special case of graphs G of independence number α(G) = 2. We present some results in this special case.
LA - eng
KW - Hadwiger's Conjecture; complete minor; independence number; connected matching; Hadwiger's conjecture; -critical graph
UR - http://eudml.org/doc/270755
ER -

References

top
  1. [1] C. Berge, Alternating chain methods: a survey, in: Graph Theory and Computing, ed., R. Read (Academic Press, New York, 1972) 1-13. Zbl0245.05115
  2. [2] S. Brandt, On the structure of dense triangle-free graphs, Combin. Prob. Comput. 8 (1999) 237-245, doi: 10.1017/S0963548399003831. Zbl0942.05032
  3. [3] S. Brandt and T. Pisanski, Another infinite sequence of dense triangle-free graphs, Elect. J. Combin. 5 (1998) #R43 1-5. Zbl0898.05067
  4. [4] P.A. Catlin, Hajós' graph-coloring conjecture: variations and counterexamples, J. Combin. Theory (B) 26 (1979) 268-274, doi: 10.1016/0095-8956(79)90062-5. Zbl0385.05033
  5. [5] G.A. Dirac, Some theorems on abstract graphs, Proc. London Math. Soc. 2 (1952) 69-81, doi: 10.1112/plms/s3-2.1.69. Zbl0047.17001
  6. [6] G.A. Dirac, Trennende Knotenpunktmengen und Reduzibilität abstrakter Graphen mit Anwendung auf das Vierfarbenproblem, J. Reine Angew. Math. 204 (1960) 116-131, doi: 10.1515/crll.1960.204.116. 
  7. [7] P. Duchet and H. Meyniel, On Hadwiger's number and the stability number, Ann. Discrete Math. 13 (1982), 71-74. Zbl0522.05060
  8. [8] T. Gallai, Kritische Graphen II, Publ. Math. Inst. Hung. Acad. 8 (1963) 373-395. 
  9. [9] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (W.H. Freeman and Company, San Francisco, 1979). Zbl0411.68039
  10. [10] H. Hadwiger, Über eine Klassifikation der Streckenkomplexe, Vierteljahrsschrift der Naturf. Gesellschaft in Zürich 88 (1943) 133-142. Zbl0061.41308
  11. [11] J.H. Kim, The Ramsey number R(3,t) has order of magnitude t²/log t, Random Struct. Algorithms 7 (1995) 173-207, doi: 10.1002/rsa.3240070302. Zbl0832.05084
  12. [12] U. Krusenstjerna-Hafstrø m and B. Toft, Some remarks on Hadwiger's Conjecture and its relation to a conjecture of Lovász, in: The Theory and Applications of Graphs: Proceedings of the Fourth International Graph Theory Conference, Kalamazoo, 1980, eds., G. Chartrand, Y. Alavi, D.L. Goldsmith, L. Leśniak-Foster and D.R. Lick (John Wiley and Sons, 1981) 449-459. 
  13. [13] L. Lovász and M.D. Plummer, Matching Theory, Akadémiai Kiadó, Budapest and Ann. Discrete Math. 29 (North-Holland, Amsterdam, 1986) 448. 
  14. [14] W. Mader, Über trennende Eckenmengen in homomorphiekritischen Graphen, Math. Ann. 175 (1968) 243-252, doi: 10.1007/BF02052726. Zbl0171.22406
  15. [15] J. Pach, Graphs whose every independent set has a common neighbor, Discrete Math. 37 (1981) 217-228, doi: 10.1016/0012-365X(81)90221-1. Zbl0473.05054
  16. [16] N. Robertson, P.D. Seymour and R. Thomas, Hadwiger's conjecture for K₆-free graphs, Combinatorica 13 (1993) 279-362, doi: 10.1007/BF01202354. Zbl0830.05028
  17. [17] B. Toft, On separating sets of edges in contraction-critical graphs, Math. Ann. 196 (1972) 129-147, doi: 10.1007/BF01419610. Zbl0219.05059
  18. [18] B. Toft, A survey of Hadwiger's Conjecture, Congr. Numer. 115 (1996) 249-283. Zbl0895.05025

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.