Kneser Graph

The Kneser graph, written with two parameters n and k, has as its vertices all the k-element subsets of a set of n elements, with an edge joining two vertices exactly when the corresponding subsets are disjoint from one another. It is named after the German mathematician Martin Kneser, who in 1955 posed the problem of finding the chromatic number of these graphs, the fewest colors needed to color the vertices so that no edge joins two vertices of the same color. The Kneser conjecture, that the chromatic number equals n minus two times k plus two, resisted ordinary combinatorial proof for over twenty years until the Hungarian mathematician Laszlo Lovasz proved it in 1978 using the Borsuk-Ulam theorem from algebraic topology, a landmark result that founded the field of topological combinatorics. The Petersen graph, itself a well known object in graph theory, is the particular Kneser graph obtained by taking n equal to five and k equal to two.