Kneser Graph - Properties

Properties

• The Kneser graph is vertex transitive and edge transitive. Each vertex has exactly neighbors. However, the Kneser graph is not, in general, a strongly regular graph, as different pairs of nonadjacent vertices have different numbers of common neighbors depending on the size of the intersection of the corresponding pair of sets.
• As Kneser (1955) conjectured, the chromatic number of the Kneser graph KG_n,k is exactly n − 2k + 2; for instance, the Petersen graph requires three colors in any proper coloring. László Lovász (1978) proved this using topological methods, giving rise to the field of topological combinatorics. Soon thereafter Imre Bárány (1978) gave a simple proof, using the Borsuk–Ulam theorem and a lemma of David Gale, and Greene (2002) won the Morgan Prize for a further simplified but still topological proof. Matoušek (2004) found a purely combinatorial proof.
• When n ≥ 3k, the Kneser graph KG_n,k always contains a Hamiltonian cycle (Chen 2000). Computational searches have found that all connected Kneser graphs for n ≤ 27, except for the Petersen graph, are Hamiltonian (Shields 2004).
• When n < 3k, the Kneser graph contains no triangles. More generally, although the Kneser graph always contains cycles of length four whenever n ≥ 2k + 2, for values of n close to 2k the shortest odd cycle may have nonconstant length (Denley 1997).
• The diameter of a connected Kneser graph KG_n,k is

  (Valencia-Pabon & Vera 2005).

• The graph spectrum of the Kneser graph KG_n,k is given as follows:

For, the eigenvalue occurs with multiplicity for and 1 for . See this paper for a proof.