Kneser graphs

Let $k,n$ be positive integers with $k\le n$. The Kneser graph $K_{n:k}$ has as its vertex set the $\left(\genfrac{}{}{0pt}{}{n}{k}\right)$ $k$-element subsets of $\{1,2,\mathrm{\dots },n\}$. Two vertices are adjacent if and only if they correspond to disjoint subsets.

The graph $K_{n:1}$ is the complete graph on $n$ vertices. Another well-known Kneser graph is $K_{5:2}$, better known as the Petersen graph, which is shown in figure 1. The Petersen graph is often a counterexample to graph-theoretical conjectures.

Figure 1: The Petersen graph

Title	Kneser graphs
Canonical name	KneserGraphs
Date of creation	2013-03-22 14:16:49
Last modified on	2013-03-22 14:16:49
Owner	justice (4961)
Last modified by	justice (4961)
Numerical id	5
Author	justice (4961)
Entry type	Definition
Classification	msc 05C99
Defines	Petersen graph