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 ≥ 2k + 1 ≥ 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.