Kneser graph

Kneser graph
The Kneser graph K(5, 2), isomorphic to the Petersen graph
Named after	Martin Kneser
Vertices	${\displaystyle {\binom {n}{k}}}$
Edges	${\displaystyle {\frac {1}{2}}{\binom {n}{k}}{\binom {n-k}{k}}}$
Chromatic number	${\displaystyle {\begin{cases}n-2k+2&n\geq 2k\\1&n<2k\end{cases}}}$
Properties	${\displaystyle {\tbinom {n-k}{k}}}$-regular arc-transitive
Notation	K(n, k), KGn,k.
Table of graphs and parameters

In graph theory, the Kneser graph K(n, k) (alternatively 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 1956.