Hadwiger's conjecture for \(K_ 6\)-free graphs

DOI10.1007/BF01202354zbMath0830.05028WikidataQ55881141 ScholiaQ55881141MaRDI QIDQ1311018

Neil Robertson, Robin Thomas, P. D. Seymour

Publication date: 18 January 1996

Published in: Combinatorica (Search for Journal in Brave)

zbMATH Keywords

chromatic number; planar; Hadwiger's conjecture; four-colour theorem; contractible; four-colour conjecture; theorem of Wagner

Mathematics Subject Classification ID

05C75: Structural characterization of families of graphs

05C15: Coloring of graphs and hypergraphs

Related Items

Fractional colouring and Hadwiger's conjecture, Clique minors in graphs and their complements

Cites Work

• Unnamed Item
• Hadwiger's conjecture (ḵ\(=6):\) Neighbour configurations of 6-vertices in contraction-critical graphs
• Disjoint paths in graphs
• 2-linked graphs
• Conjecture de Hadwiger: \(k=6\). II: Réductions de sommets de degré 6 dans les graphes 6-chromatiques contraction-critiques. (Hardwiger's conjecture: \(k=6\). II: Reductions of 6-vertices in 6-chromatic contraction-critical graphs)
• Über die Maximalzahl kreuzungsfreier H-Wege
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Graph minors. IX: Disjoint crossed paths
• Homomorphiesätze für Graphen
• Über trennende Eckenmengen in homomorphiekritischen Graphen
• A Polynomial Solution to the Undirected Two Paths Problem
• The Factorization of Linear Graphs
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs