Kneser graph

In graph theory, the Kneser graph (alternatively ) is the graph whose vertices correspond to the -element subsets of a set of elements, and where two vertices are adjacent if and only if the two corresponding sets are disjoint. Kneser graphs are named after Martin Kneser, who first investigated them in 1955.
Examples.
The Kneser graph is the complete graph on vertices.
The Kneser graph is the complement of the line graph of the complete graph on vertices.
The Kneser graph is the odd graph ; in particular is the Petersen graph (see top right figure).
The Kneser graph , visualized on the right.
Properties.
Chromatic number.
As conjectured, the chromatic number of the Kneser graph for formula_4 is exactly ; for instance, the Petersen graph requires three colors in any proper coloring. This conjecture was proved in several ways.
When formula_5, the chromatic number of is 1.
Diameter.
Spectrum
Related graphs.
The Johnson graph is the graph whose vertices are the -element subsets of an -element set, two vertices being adjacent when they meet in a -element set. The Johnson graph is the complement of the Kneser graph . Johnson graphs are closely related to the Johnson scheme, both of which are named after Selmer M. Johnson.
The generalized Kneser graph has the same vertex set as the Kneser graph , but connects two vertices whenever they correspond to sets that intersect in or fewer items . Thus .
The bipartite Kneser graph has as vertices the sets of and items drawn from a collection of elements. Two vertices are connected by an edge whenever one set is a subset of the other. Like the Kneser graph it is vertex transitive with degree formula_18 The bipartite Kneser graph can be formed as a bipartite double cover of in which one makes two copies of each vertex and replaces each edge by a pair of edges connecting corresponding pairs of vertices . The bipartite Kneser graph is the Desargues graph and the bipartite Kneser graph is a crown graph.