2001 | OriginalPaper | Chapter
Kneser Graphs
Authors : Chris Godsil, Gordon Royle
Published in: Algebraic Graph Theory
Publisher: Springer New York
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The Kneser graph K v:r is the graph with the r-subsets of a fixed v-set as its vertices, with two r-subsets adjacent if they are disjoint. We have already met the complete graphs K v:1, while K v:2 is the complement of the line graph of K v . The first half of this chapter is devoted to fractional versions of the chromatic number and clique number of a graph. We discover that for the fractional chromatic number, the Kneser graphs play a role analogous to that played by the complete graphs for the ordinary chromatic number. We use this setting to provide a proof of the Erdős-Ko-Rado theorem, which is a famous result from extremal set theory. In the remainder of the chapter, we determine the chromatic number of the Kneser graphs, which surprisingly uses a nontrivial result from topology, and study homomorphisms between Kneser graphs.