Article ID Journal Published Year Pages File Type
4654505 European Journal of Combinatorics 2007 4 Pages PDF
Abstract

C. Thomassen showed that powers of certain cycles are counterexamples to Hajós’ conjecture. We prove that powers of cycles and their complements satisfy Hadwiger’s conjecture, that is, every kk-chromatic graph has a kk-clique as a minor.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Preview
Hadwiger’s conjecture for powers of cycles and their complements
Authors
, ,