Kneser graph

Examples

Properties

• The Kneser graph has vertices. Each vertex has exactly neighbors.
• The Kneser graph is vertex transitive and arc transitive. However, it 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.
• Because Kneser graphs are regular and edge-transitive, their vertex connectivity equals their degree, except for which is disconnected. More precisely, the connectivity of is the same as the number of neighbors per vertex.
• As conjectured, the chromatic number of the Kneser graph for is exactly ; for instance, the Petersen graph requires three colors in any proper coloring. proved this using topological methods, giving rise to the field of topological combinatorics. Soon thereafter gave a simple proof, using the Borsuk–Ulam theorem and a lemma of David Gale, and won the Morgan Prize for a further simplified but still topological proof. found a purely combinatorial proof.
• The Kneser graph contains a Hamiltonian cycle if :
• The Kneser graph contains a Hamiltonian cycle if there exists a non-negative integer a such that . In particular, the odd graph has a Hamiltonian cycle if.
• With the exception of the Petersen graph, all connected Kneser graphs with are Hamiltonian.
• When, the Kneser graph contains no triangles. More generally, when it does not contain cliques of size, whereas it does contain such cliques when. Moreover, although the Kneser graph always contains cycles of length four whenever, for values of close to the shortest odd cycle may have nonconstant length.
• The diameter of a connected Kneser graph is :
• The spectrum of the Kneser graph consists of k + 1 distinct eigenvalues:
• The Erdős–Ko–Rado theorem states that the independence number of the Kneser graph for is

  Related graphs