Hadwiger's conjecture for \(K_ 6\)-free graphs (Q1311018): Difference between revisions

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.