The Kneser graphs are a class of graph introduced by Lovász (1978) to prove Kneser's conjecture. Given two positive integers
and , the Kneser graph , often denoted (Godsil and Royle 2001; Pirnazar and Ullman 2002; Scheinerman
and Ullman 2011, pp. 31-32), is the graph whose vertices represent the -subsets of , and where two vertices are connected if and only
if they correspond to disjoint subsets. therefore has vertices and is regular of degree .
is connected for . For nonempty Kneser graphs (i.e., ), the chromatic number
is given by ,
as conjectured by Kneser (1956) and proved by Lovász (1978), Bárány
(1978), Greene (2002), and Matoušek (2004).
Chen and Lih (1987) showed that is symmetric. It has
long been conjectured that is Hamiltonian (with the exception of ) for , and this was verified by Shields and Savage (2004)
for .
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. A25,
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 ." J. Combin. Th. Ser.
B80, 69-79, 2000.Chen, B. L. and Lih, K.-W. "Hamiltonian
Uniform Subset Graphs." J. Combin. Th. Ser. B42, 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. Monthly109,
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. A2, 89-98, 1978.Kneser, M. "Aufgabe 300."
Jahresber. Deutsch. Math.-Verein58, 1955.Lovász,
L. "Kneser's Conjecture, Chromatic Numbers and Homotopy." J. Comb. Th.
A25, 319-324, 1978.Matoušek, J. "A Combinatorial
Proof of Kneser's Conjecture." Combinatorica24, 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.