TOPICS
Search

Kneser Graph


KneserGraphs

The Kneser graphs are a class of graph introduced by Lovász (1978) to prove Kneser's conjecture. Given two positive integers n and k, the Kneser graph K(n,k), often denoted K_(n:k) (Godsil and Royle 2001; Pirnazar and Ullman 2002; Scheinerman and Ullman 2011, pp. 31-32), is the graph whose vertices represent the k-subsets of {1,...,n}, and where two vertices are connected if and only if they correspond to disjoint subsets. K(n,k) therefore has (n; k) vertices and is regular of degree (n-k; k).

K(n,k) is connected for n>2k. For nonempty Kneser graphs (i.e., n!=k+1), the chromatic number is given by n-2k+2, as conjectured by Kneser (1956) and proved by Lovász (1978), Bárány (1978), Greene (2002), and Matoušek (2004).

K(n,k) has clique number

 omega(K(n,k))=|_n/k_|.
(1)

This follows from a generalization of Baranyai's theorem, which gives omega(K(n,k))=(n-1; k-1) for k|n, by Brouwer and Schrijver (1979). As a result, the clique covering number is

theta(K(n,k))=[(|K(n,k)|)/(omega(K(n,k)))]
(2)
=[((n; k))/(|_n/k_|)]
(3)

(S. Wagon, pers. comm., Feb. 12, 2013). The fractional chromatic number of nonempty Kneser graphs K(n,k) is n/k (Scheinerman and Ullman 2011, p. 32).

Similarly, the independence number for a non-empty Kneser graph is given by

 alpha(K(n,k))=(n-1; k-1)
(4)

by the Erdős-Ko-Rado theorem (Aigner and Ziegler 2000, p.  251).

Östergård et al. (2015) give bounds on the domination numbers of Kneser graphs, together with a number of exact values for smaller cases.

The Kneser graph is the generalization of the odd graph, with the odd graph O_n corresponding to K(2n-1,n-1). Special cases are summarized in the table below.

The Kneser graph K(n,2) is a distance-regular with intersection array {(n-2)(n-3)/2,2n-8;1,(n-3)(n-4)/2}.

Chen and Lih (1987) showed that K(n,k) is symmetric. It has long been conjectured that K(n,k) is Hamiltonian (with the exception of K(5,2)) for n>2k, and this was verified by Shields and Savage (2004) for n<=27.

K(7,2) is one of the three locally Petersen graphs (Hall 1980).

The bipartite double graph of K(n,k) is the bipartite Kneser graph H(n,k).

The (n,k)-Kneser graph is implemented in the Wolfram Language as GraphData[{"Kneser", {n, k}}].


See also

Bipartite Kneser Graph, Kneser's Conjecture, Locally Petersen Graph, Odd Graph, Petersen Graph

Portions of this entry contributed by Margherita Barile

Explore with Wolfram|Alpha

References

Aigner, M. and Ziegler, G. M. "The Chromatic Number of Kneser Graphs." Ch. 38 in Proofs from the Book, 2nd ed. New York: Springer-Verlag, pp. 251-256, 2000.Bárány, I. "A Short Proof of Kneser's Conjecture." J. Combin. Th., Ser. A 25, 325-326, 1978.Brouwer, A. E. "Kneser Graphs." http://www.win.tue.nl/~aeb/drg/graphs/Kneser.html.Brouwer, A. E. and Schrijver, A. "Uniform Hypergraphs." In Packing and Covering in Combinatorics. Mathematical Centre Tracts, No. 106, pp. 39-73, 1979.Chen, Y.-C. "Kneser Graphs Are Hamiltonian for n>=3k." J. Combin. Th. Ser. B 80, 69-79, 2000.Chen, B. L. and Lih, K.-W. "Hamiltonian Uniform Subset Graphs." J. Combin. Th. Ser. B 42, 257-263, 1987.DistanceRegular.org. "Kneser Graphs." http://www.distanceregular.org/indexes/knesergraphs.html.Godsil, C. and Royle, G. "Kneser Graphs." Ch. 7 in Algebraic Graph Theory. New York: Springer-Verlag, pp. 135-161, 2001.Greene, J. E. "A New Short Proof of Kneser's Conjecture." Amer. Math. Monthly 109, 918-920, 2002.Hall, J. I. "Locally Petersen Graphs." J. Graph Th. 4, 173-187, 1980.Heinrich, K. and Wallis, W. D. "Hamiltonian Cycles in Certain Graphs." J. Austral. Math. Soc. Ser. A 2, 89-98, 1978.Kneser, M. "Aufgabe 300." Jahresber. Deutsch. Math.-Verein 58, 1955.Lovász, L. "Kneser's Conjecture, Chromatic Numbers and Homotopy." J. Comb. Th. A 25, 319-324, 1978.Matoušek, J. "A Combinatorial Proof of Kneser's Conjecture." Combinatorica 24, 163-170, 2004.Mütze, T. "On Hamilton Cycles in Graphs Defined by Intersecting Set Systems." Not. Amer. Soc. 74, 583-592, 2024.Östergård, P. R. J.; Shao, Z.; and Xu, X. "Bounds on the Domination Number of Kneser Graphs." Ars Math. Contemp. 9, 197-205, 2015.Phillips, D. "Kneser Graph Maximal Neighbour Simplexes." http://www.ucalgary.ca/~phillips/users/sali/kneser.html.Pirnazar, A. and Ullman, D. H. "Girth and Fractional Chromatic Number of Planar Graphs." J. Graph Th. 39, 201-217, 2002.Scheinerman, E. R. and Ullman, D. H. Fractional Graph Theory A Rational Approach to the Theory of Graphs. New York: Dover, 2011.Shields, I. and Savage, C. D. "A Note on Hamilton Cycles in Kneser Graphs." Bull. Inst. Combin. Appl. 40, 13-22, 2004.

Referenced on Wolfram|Alpha

Kneser Graph

Cite this as:

Barile, Margherita and Weisstein, Eric W. "Kneser Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/KneserGraph.html

Subject classifications