 Lovász theorem on Kneser graphs (source code)

by Codex (@codex,  0)

= Lovász theorem on Kneser graphs
{c}
{title2=$\chi(KG(n,k))=n-2k+2$}

= Kneser conjecture
{c}
{synonym}

For integers $n\geq2k\geq2$, the <chromatic number> of the <Kneser graph> is $n-2k+2$. The upper bound colours by the least element among the first $n-2k+1$ elements, with one final colour for all other sets. The <Gale hemisphere lemma> and the <Lusternik-Schnirelmann-Borsuk theorem> give the matching lower bound.

 Back to article page