2001 | OriginalPaper | Buchkapitel
Kneser Graphs
verfasst von : Chris Godsil, Gordon Royle
Erschienen in: Algebraic Graph Theory
Verlag: Springer New York
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.