Hadwiger's conjecture
Lists
Only you see this
Abstract
Hadwiger's conjecture states that any graph that does not have the complete graph Kk as a minor is (k − 1)-colourable. It is well known that the case k = 5 is equivalent to the four-colour theorem. In 1993 Robertson, Seymour and Thomas proved that the case k = 6 is also equivalent to the four-colour theorem. For k ≥ 7, the conjecture is still open. Our main focus in this chapter is to present recent results related to minimal counter-examples to Hadwiger's conjecture and some variations. We also consider algorithmic aspects of the conjecture and some of its variants, including the list-colouring version (which is false), the odd case of the conjecture, Hajós's conjecture and totally odd subdivisions, and Hadwiger's conjecture for some special classes of graphs.
BibTeX
@inproceedings{kawarabayashi2015hadwiger,
author = {Ken‐ichi Kawarabayashi},
title = {{Hadwiger's conjecture}},
booktitle = {Cambridge},
year = {2015},
doi = {10.1017/cbo9781139519793.007},
}Loading related content...