On the Chromatic Number of the Square of the Kneser Graph <Emphasis Type="Italic">K</Emphasis>(2<Emphasis Type="Italic">k</Emphasis>+1, <Emphasis Type="Italic">k</Emphasis>) |
| |
Authors: | Email author" target="_blank">Seog-Jin?KimEmail author Kittikorn?Nakprasit |
| |
Institution: | (1) Department of Mathematics, University of Illinois, Urbana, IL 61801, USA |
| |
Abstract: | The Kneser graph K(n, k) is the graph whose vertices are the k-element subsets of an n-element set, with two vertices adjacent if the sets are disjoint. The chromatic number of the Kneser graph K(n, k) is n–2k+2. Zoltán Füredi raised the question of determining the chromatic number of the square of the Kneser graph, where the square of a graph is the graph obtained by adding edges joining vertices at distance at most 2. We prove that (K2(2k+1, k)) 4k when k is odd and (K2(2k+1, k)) 4k+2 when k is even. Also, we use intersecting families of sets to prove lower bounds on (K2(2k+1, k)), and we find the exact maximum size of an intersecting family of 4-sets in a 9-element set such that no two members of the family share three elements.This work was partially supported by NSF grant DMS-0099608Final version received: April 23, 2003 |
| |
Keywords: | Kneser graph Square Graph coloring Intersecting family |
本文献已被 SpringerLink 等数据库收录! |
|