×

zbMATH — the first resource for mathematics

Hadwiger’s conjecture for \(K_ 6\)-free graphs. (English) Zbl 0830.05028
Hadwiger conjectured in 1943 that every graph of chromatic number \(n\) is contractible to the complete graph on \(n\) vertices. A theorem of Wagner from 1937 implied that Hadwiger’s conjecture for \(n= 5\) is equivalent to the four-colour conjecture. The authors now reduce the case \(n= 6\) also to the four-colour theorem. They consider a minimal counterexample \(H\) to Hadwiger’s conjecture for \(n= 6\), and show in a complicated proof that there must exist a vertex \(z\) in \(H\) such that \(H- z\) is planar. So the four-colour theorem implies that \(H\) cannot exist.
Reviewer: W.Mader (Hannover)

MSC:
05C15 Coloring of graphs and hypergraphs
05C75 Structural characterization of families of graphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] K. Appel, andW. Haken: Every planar map is four colorable. Part I. Discharging,Illinois J. Math. 21 (1977), 429-490. · Zbl 0387.05009
[2] K. Appel, W. Haken, andJ. Koch: Every planar map is four colorable. Part II. Reducibility,Illinois J. Math. 21 (1977), 491-567. · Zbl 0387.05010
[3] G. A. Dirac: A property of 4-chromatic graphs and some remarks on critical graphs,J. London Math. Soc. 27 (1952), 85-92. · Zbl 0046.41001 · doi:10.1112/jlms/s1-27.1.85
[4] H. Hadwiger: Über eine Klassifikation der Streckenkomplexe,Vierteljahrsschr. Naturforsch. Ges. Zürich 88 (1943), 133-142. · Zbl 0061.41308
[5] L. Jørgensen: Contractions toK 8,J. Graph Theory, to appear.
[6] H. A. Jung: Eine Verallgemeinerung desn-fachen Zusammenhangs für Graphen,Math. Ann. 187 (1970), 95-103. · Zbl 0191.22501 · doi:10.1007/BF01350174
[7] W. Mader: Homomorphiesätze für Graphen,Math. Ann. 178 (1968), 154-168. · Zbl 0165.57401 · doi:10.1007/BF01350657
[8] W. Mader: Über die Maximalzahl kreuzungsfreierH-Wege,Arch. Math. (Basel) 31 (1978), 387-402. · Zbl 0378.05038
[9] W. Mader: Über trennende Eckenmengen in homomorphiekritischen Graphen,Math. Ann. 175 (1968), 243-252. · Zbl 0171.22406 · doi:10.1007/BF02052726
[10] J. Mayer: Conjecture de Hadwiger:k=6. II-Réductions de sommets de degré 6 dans les graphes 6-chromatiques contraction-critiques.Discrete Math. 101 (1992), 213-222. · Zbl 0753.05036 · doi:10.1016/0012-365X(92)90604-E
[11] J. Mayer: Hadwiger’s conjecture (k=6): neighbour configurations of 6-vertices in contraction-critical graphs,Discrete Math. 74 (1989), 137-148. · Zbl 0672.05026 · doi:10.1016/0012-365X(89)90205-7
[12] N. Robertson, andP. D. Seymour: Graph Minors. IX. Disjoint crossed paths,J. Combinatorial Theory, Ser. B,49 (1989), 40-77. · Zbl 0741.05044 · doi:10.1016/0095-8956(90)90063-6
[13] P. D. Seymour: Disjoint paths in graphs,Discrete Math. 29 (1980), 293-309. · Zbl 0457.05043 · doi:10.1016/0012-365X(80)90158-2
[14] Y. Shiloach: A polynomial solution to the undirected two paths problem,J. Assoc. Comp. Mach. 27 (1980), 445-456. · Zbl 0475.68042
[15] C. Thomassen: 2-linked graphs,European J. Combinatorics 1 (1980), 371-378. · Zbl 0457.05044
[16] W. T. Tutte: The factorization of linear graphs,J. London Math. Soc. 22 (1947), 107-111. · Zbl 0029.23301 · doi:10.1112/jlms/s1-22.2.107
[17] K. Wagner: Über eine Eigenschaft der ebenen Komplexe,Math. Ann. 114 (1937), 570-590. · JFM 63.0550.01 · doi:10.1007/BF01594196
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.