Hadwiger's conjecture for the complements of Kneser graphs

Guangjun Xu, Sanming Zhou

Published 2015-03-24Version 1

Hadwiger's conjecture asserts that every graph with chromatic number $t$ contains a complete minor of order $t$. Given integers $n \ge 2k+1 \ge 5$, the Kneser graph $K(n, k)$ is the graph with vertices the $k$-subsets of an $n$-set such that two vertices are adjacent if and only if the corresponding $k$-subsets are disjoint. We prove that Hadwiger's conjecture is true for the complements of Kneser graphs.