Hadwiger's Conjecture for the Complements of Kneser Graphs |
| |
| Authors: | Guangjun Xu Sanming Zhou |
| |
| Affiliation: | 1. SCHOOL OF MATHEMATICS AND COMPUTING SCIENCE, ZUNYI NORMAL COLLEGE, ZUNYI, CHINA;2. SCHOOL OF MATHEMATICS AND STATISTICS, THE UNIVERSITY OF MELBOURNE, PARKVILLE, VIC, AUSTRALIA |
| |
| Abstract: | 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. |
| |
| Keywords: | Hadwiger's conjecture graph coloring graph minor Kneser graph |
|
|
, 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.