# The chromatic number of the Kneser graphs and the q-Kneser graphs

This year is László Lovász‘s 70th birthday and I went to his birthday conference, so a blog post about one of his famous results seems to be appropriate: the chromatic number of the Kneser graph.

Let $\Gamma$ be a graph with a vertex set $V$ and an adjacency relation $\sim$. A coloring of $\Gamma$ is a map from $V$ from $V$ to a set of colors $C$ such that no pair of adjacent vertices gets mapped to the same element of $C$. The chromatic number of $\Gamma$ is the smallest number of colors needed to color $\Gamma$. One of the nicest graphs to investigate is the Kneser graph: Here $V$ consists of all subsets of $\{ 1, 2, \ldots, n \}$ of size $k$ and two vertices are adjacent if the corresponding $k$-sets are disjoint. For $k=2$ and $n=5$, this is the famous Petersen graph: