Hadwiger's conjecture

Ken‐ichi KawarabayashiCambridge 2015 · DOI · OpenAlex

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...

Figure