Kneser Graph

The Kneser graphs are a class of graph introduced by Lovász (1978) to prove Kneser's conjecture. Given two positive integers and , the Kneser graph , often denoted (Godsil and Royle 2001; Pirnazar and Ullman 2002; Scheinerman and Ullman 2011, pp. 31-32), is the graph whose vertices represent the -subsets of , and where two vertices are connected if and only if they correspond to disjoint subsets. therefore has vertices and is regular of degree .

is connected for . For nonempty Kneser graphs (i.e., ), the chromatic number is given by , as conjectured by Kneser (1956) and proved by Lovász (1978), Bárány (1978), Greene (2002), and Matoušek (2004).

has clique number

(1)

This follows from a generalization of Baranyai's theorem, which gives for , by Brouwer and Schrijver (1979). As a result, the clique covering number is

			(2)
			(3)

(S. Wagon, pers. comm., Feb. 12, 2013). The fractional chromatic number of nonempty Kneser graphs is (Scheinerman and Ullman 2011, p. 32).

Similarly, the independence number for a non-empty Kneser graph is given by

(4)

by the Erdős-Ko-Rado theorem (Aigner and Ziegler 2000, p.  251).

Östergård et al. (2015) give bounds on the domination numbers of Kneser graphs, together with a number of exact values for smaller cases.

The Kneser graph is the generalization of the odd graph, with the odd graph corresponding to . Special cases are summarized in the table below.

	special case
	Petersen graph
	-complete graph
	-empty graph
	ladder rung graph

The Kneser graph is a distance-regular with intersection array .

Chen and Lih (1987) showed that is symmetric. It has long been conjectured that is Hamiltonian (with the exception of ) for , and this was verified by Shields and Savage (2004) for .

is one of the three locally Petersen graphs (Hall 1980).

The bipartite double graph of is the bipartite Kneser graph .

The -Kneser graph is implemented in the Wolfram Language as GraphData["Kneser", n, k].