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 be a graph with a vertex set and an adjacency relation . A coloring of is a map from from to a set of colors such that no pair of adjacent vertices gets mapped to the same element of . The chromatic number of is the smallest number of colors needed to color . One of the nicest graphs to investigate is the Kneser graph: Here consists of all subsets of of size and two vertices are adjacent if the corresponding -sets are disjoint. For and , this is the famous Petersen graph:

Advertisements