Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Kneser graph
Summary
In graph theory, the Kneser graph K(n, k) (alternatively KGn,k) is the graph whose vertices correspond to the k-element subsets of a set of n 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 1956.
The Kneser graph K(n, 1) is the complete graph on n vertices.
The Kneser graph K(n, 2) is the complement of the line graph of the complete graph on n vertices.
The Kneser graph K(2n − 1, n − 1) is the odd graph On; in particular O3 = K(5, 2) is the Petersen graph (see top right figure).
The Kneser graph O4 = K(7, 3), visualized on the right.
The Kneser graph has vertices. Each vertex has exactly neighbors.
The Kneser graph is vertex transitive and arc transitive. When , the Kneser graph is a strongly regular graph, with parameters . However, it is not strongly regular when , as different pairs of nonadjacent vertices have different numbers of common neighbors depending on the size of the intersection of the corresponding pairs 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 n − 2k + 2; for instance, the Petersen graph requires three colors in any proper coloring. This conjecture was proved in several ways.
László Lovász proved this in 1978 using topological methods, giving rise to the field of topological combinatorics.
Soon thereafter Imre Bárány gave a simple proof, using the Borsuk–Ulam theorem and a lemma of David Gale.
Joshua E. Greene won the 2002 the Morgan Prize for outstanding undergraduate research for his further simplified but still topological proof.
In 2004, Jiří Matoušek found a purely combinatorial proof.
In contrast, the fractional chromatic number of these graphs is .
When , has no edges and its chromatic number is 1.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.