Kneser graph

Kneser graph
The Kneser graph KG5,2, isomorphic to the Petersen graph
Named after	Martin Kneser
Vertices	${\displaystyle \textstyle {\binom {n}{k}}}$
Edges	${\displaystyle \textstyle {\binom {n}{k}}{\binom {n-k}{k}}/2}$
Chromatic number	${\displaystyle \left\{{\begin{array}{ll}n-2k+2&n\geq 2k\\1&{\text{otherwise}}\end{array}}\right.}$
Properties	${\displaystyle \textstyle {\binom {n-k}{k}}}$-regular arc-transitive
Notation	KGn,k, K(n,k)

In graph theory, the Kneser graph KG_n,k is the graph whose vertices correspond to the k-element subsets of a set of n elements, and where two vertices are adjacent if and only if the two corresponding sets are disjoint. Kneser graphs are named after Martin Kneser, who first investigated them in 1955.

The complete graph on n vertices is the Kneser graph KG_n,1.

The complement of the line graph of the complete graph on n vertices is the Kneser graph KG_n,2.

The Kneser graph KG_{2n − 1,n − 1} is known as the odd graph O_n; the odd graph O₃ = KG_5,2 is isomorphic to the Petersen graph.

The Johnson graph J_n,k is the graph whose vertices are the k-element subsets of an n-element set, two vertices being adjacent when they meet in a (k − 1)-element set. For k = 2 the Johnson graph is the complement of the Kneser graph KG_n,2. Johnson graphs are closely related to the Johnson scheme, both of which are named after Selmer M. Johnson.

The generalized Kneser graph KG_n,k,s has the same vertex set as the Kneser graph KG_n,k, but connects two vertices whenever they correspond to sets that intersect in s or fewer items (Denley 1997). Thus KG_n,k,0 = KG_n,k.