Hadwiger's conjecture for the complements of Kneser graphs

Abstract

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.

This is the final version to be published in J. Graph Theory