Geodesic
On a special case of Hadwiger's conjecture
Discussiones Mathematicae. Graph Theory, Tome 23 (2003) no. 2, pp. 333-363.

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

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.
Keywords: Hadwiger's Conjecture, complete minor, independence number, connected matching 
@article{DMGT_2003_23_2_a9,
     author = {Plummer, Michael and Stiebitz, Michael and Toft, Bjarne},
     title = {On a special case of {Hadwiger's} conjecture},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {333--363},
     publisher = {mathdoc},
     volume = {23},
     number = {2},
     year = {2003},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2003_23_2_a9/}
}
TY  - JOUR
AU  - Plummer, Michael
AU  - Stiebitz, Michael
AU  - Toft, Bjarne
TI  - On a special case of Hadwiger's conjecture
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2003
SP  - 333
EP  - 363
VL  - 23
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2003_23_2_a9/
LA  - en
ID  - DMGT_2003_23_2_a9
ER  - 
%0 Journal Article
%A Plummer, Michael
%A Stiebitz, Michael
%A Toft, Bjarne
%T On a special case of Hadwiger's conjecture
%J Discussiones Mathematicae. Graph Theory
%D 2003
%P 333-363
%V 23
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2003_23_2_a9/
%G en
%F DMGT_2003_23_2_a9
Plummer, Michael; Stiebitz, Michael; Toft, Bjarne. On a special case of Hadwiger's conjecture. Discussiones Mathematicae. Graph Theory, Tome 23 (2003) no. 2, pp. 333-363. http://geodesic.mathdoc.fr/item/DMGT_2003_23_2_a9/

[1] C. Berge, Alternating chain methods: a survey, in: Graph Theory and Computing, ed., R. Read (Academic Press, New York, 1972) 1-13.

[2] S. Brandt, On the structure of dense triangle-free graphs, Combin. Prob. Comput. 8 (1999) 237-245, doi: 10.1017/S0963548399003831.

[3] S. Brandt and T. Pisanski, Another infinite sequence of dense triangle-free graphs, Elect. J. Combin. 5 (1998) #R43 1-5.

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

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

[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] P. Duchet and H. Meyniel, On Hadwiger's number and the stability number, Ann. Discrete Math. 13 (1982), 71-74.

[8] T. Gallai, Kritische Graphen II, Publ. Math. Inst. Hung. Acad. 8 (1963) 373-395.

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

[10] H. Hadwiger, Über eine Klassifikation der Streckenkomplexe, Vierteljahrsschrift der Naturf. Gesellschaft in Zürich 88 (1943) 133-142.

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

[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] L. Lovász and M.D. Plummer, Matching Theory, Akadémiai Kiadó, Budapest and Ann. Discrete Math. 29 (North-Holland, Amsterdam, 1986) 448.

[14] W. Mader, Über trennende Eckenmengen in homomorphiekritischen Graphen, Math. Ann. 175 (1968) 243-252, doi: 10.1007/BF02052726.

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

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

[17] B. Toft, On separating sets of edges in contraction-critical graphs, Math. Ann. 196 (1972) 129-147, doi: 10.1007/BF01419610.

[18] B. Toft, A survey of Hadwiger's Conjecture, Congr. Numer. 115 (1996) 249-283.