chromatic number

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:

400px-Kneser_graph_KG(5,2).svg (more…)