Hadwiger's Conjecture for the Complements of Kneser Graphs
Guangjun Xu, Sanming Zhou · Journal of Graph Theory · 2015
Hadwiger's conjecture asserts that every graph with chromatic number t contains a complete minor of order t. Given integers , the Kneser graph 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.