Hadwiger's conjecture for \(K_ 6\)-free graphs
type: Item
instance of: scholarly article
title: Hadwiger's conjecture for \(K_ 6\)-free graphs
zbMATH Open document ID: 0830.05028
DOI: 10.1007/BF01202354
author: Neil Robertson
author: Robin Thomas
author: Paul Seymour
published in: Combinatorica
publication date: 1996-01-18T00:00:00Z
review text: 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.
reviewed by: W. Mader
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C75
zbMATH DE Number: 484133
zbMATH Keywords: chromatic number
zbMATH Keywords: contractible
zbMATH Keywords: theorem of Wagner
zbMATH Keywords: four-colour conjecture
zbMATH Keywords: Hadwiger's conjecture
zbMATH Keywords: planar
zbMATH Keywords: four-colour theorem
Wikidata QID: Q55881141
MaRDI profile type: Publication
cites work: Every planar map is four colorable. I: Discharging
cites work: Every planar map is four colorable. II: Reducibility
cites work: A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
cites work: Q5837979
cites work: Homomorphiesätze für Graphen
cites work: Über die Maximalzahl kreuzungsfreier H-Wege
cites work: Über trennende Eckenmengen in homomorphiekritischen Graphen
cites work: Q1197029
cites work: Hadwiger's conjecture (ḵ\(=6):\) Neighbour configurations of 6-vertices in contraction-critical graphs
cites work: Graph minors. IX: Disjoint crossed paths
cites work: Disjoint paths in graphs
cites work: A Polynomial Solution to the Undirected Two Paths Problem
cites work: 2-linked graphs
cites work: The Factorization of Linear Graphs
full work available at URL: https://doi.org/10.1007/bf01202354
OpenAlex ID: W1520619927
description: scientific article; zbMATH DE number 484133