- Kneser graph
infobox graph

name = Kneser graph

image_caption = The Kneser graph "KG"_{5,2}, isomorphic to thePetersen graph

namesake =Martin Kneser

properties = arc-transitiveIngraph theory , the**Kneser graph**$KG\_\{n,k\}$ is the graph whose vertices correspond to the $k$-element subsets of a set of $n$ elements, and where two vertices are connected if and only if the two corresponding sets are disjoint. Kneser graphs are named afterMartin Kneser , who first investigated them in 1955.**Examples**The

complete graph on $n$ vertices is the Kneser graph $KG\_\{n,1\}$.The Kneser graph "KG"

_{5,2}is isomorphic to thePetersen Graph .The Kneser graph $KG\_\{2n-1,n-1\}$ is known as the

**odd graph**$O\_n$.**Properties*** The Kneser graph is a vertex-transitive and

edge-transitive graph in which each vertex has exactly $n-kchoose\; k$ neighbors. However the Kneser graph is not, in general, astrongly 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"-2"k"+2; for instance, the Petersen graph requires three colors in any proper coloring. Lovász (1978) proved this using topological methods, giving rise to the field oftopological combinatorics , and in 2002 Joshua Greene won theFrank and Brennie Morgan Prize for Outstanding Research in Mathematics by an Undergraduate Student for a simplified but still topological proof. Matoušek (2004) found a purely combinatorial proof.* When "n" ≥ 3"k", 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" < 3"k", the Kneser graph contains no triangles. More generally, although the Kneser graph always contains cycles of length four whenever "n" ≥ 2"k"+2, for values of "n" close to 2"k" the shortest odd cycle may have nonconstant length (Denley 1997).

* The

diameter of a connected Kneser graph $KG\_\{n,k\}$ is::$leftlceil\; frac\{k-1\}\{n-2k\}\; ight\; ceil\; +\; 1$:(Valencia-Pabon and Vera 2005).**Related graphs**The complement of a Kneser graph is sometimes known as a

**Johnson graph**.The

**generalized Kneser graph**$KG\_\{n,k,s\}$ has the same vertex set as the Kneser graph $KG\_\{n,k\}$, but connects two vertices whenever they correspond to sets that intersect in "s" or fewer items (Denley 1997). Thus $KG\_\{n,k,0\}=KG\_\{n,k\}$.The

**bipartite Kneser graph**$H\_\{n,k\}$ has as vertices the sets of "k" and "n"-"k" items drawn from a collection of "n" 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 $n-kchoose\; k$. The bipartite Kneser graph can be formed as a bipartite cover of $KG\_\{n,k\}$ in which one makes two copies of each vertex and replaces each edge by a pair of edges connecting corresponding pairs of vertices (Simpson 1991). The bipartite Kneser graph "H"_{5,2}is theDesargues graph .**References*** cite journal

author = Chen, Ya-Chen

journal = Journal of Combinatorial Theory, Series B

title = Kneser graphs are Hamiltonian for "n" ≥ 3"k"

volume = 80

year = 2000

pages = 69–79

url = http://math.la.asu.edu/~cchen/kneser.ps

doi = 10.1006/jctb.2000.1969* cite journal

title = The odd girth of the generalised Kneser graph

author = Denley, Tristan

journal = European Journal of Combinatorics

volume = 18

issue = 6

year = 1997

pages = 607–611

doi = 10.1006/eujc.1996.0122* cite journal

author = Greene, Joshua E.

title = A new short proof of Kneser's conjecture

journal =American Mathematical Monthly

year = 2002

volume = 109

issue = 10

pages = 918–920

doi = 10.2307/3072460* cite journal

author = Kneser, Martin

title = Aufgabe 360

journal = Jahresbericht der Deutschen Mathematiker-Vereinigung, 2. Abteilung

volume = 58

year = 1955

pages = 27* cite journal

author = Lovász, László

authorlink = László Lovász

title = Kneser's conjecture, chromatic number, and homotopy

year = 1978

volume = 25

journal = Journal of Combinatorial Theory, Series A

pages = 319–324

doi = 10.1016/0097-3165(78)90022-5* cite journal

author = Matoušek, Jiří

title = A combinatorial proof of Kneser's conjecture

journal = Combinatorica

volume = 24

issue = 1

year = 2004

pages = 163–170

doi = 10.1007/s00493-004-0011-1* cite paper

author = Shields, Ian Beaumont

title = Hamilton Cycle Heuristics in Hard Graphs

version = Ph.D. thesis

publisher =North Carolina State University

url = http://www.lib.ncsu.edu/theses/available/etd-03142004-013420/

year = 2004* cite conference

author = Simpson, J. E.

title = Hamiltonian bipartite graphs

booktitle = Proc. 22nd Southeastern Conf. Combinatorics, Graph Theory, and Computing

pages = 97–110

volume = 85

year = 1991* cite journal

title = On the diameter of Kneser graphs

author = Valencia-Pabon, Mario; Vera, Juan-Carlos

journal = Discrete Mathematics

volume = 305

issue = 1–3

pages = 383–385

year = 2005

doi = 10.1016/j.disc.2005.10.001**External links***

*

*Wikimedia Foundation.
2010.*