The Kneser graphs are a class of graph introduced by Lovász to prove Kneser's conjecture. Given two positive integers n and k, the Kneser graph K(n, k), often denoted K_(n:k) (Godsil and Royle 2001, pp. 31-32), is the graph whose vertices represent the k-subsets of {1, ..., n}, and where two vertices are connected if and only if they correspond to disjoint subsets. K(n, k) therefore has (n k) vertices and is regular of degree (n - k k). K(n, k) is connected for n>2k. For nonempty Kneser graphs (i.e., n!=k + 1), the chromatic number is given by n - 2k + 2, as conjectured by Kneser and proved by Lovász, Bárány, Greene, and Matoušek.

bipartite Kneser graph | Kneser's conjecture | locally Petersen graph | odd graph | Petersen graph