TheKneser graphK(n,k) is the graph whose vertices are thek-element subsets of ann-element set, with two vertices adjacent if the sets are disjoint. The chromatic number of the Kneser graphK(n,k) isn−2k+2. Zoltán Füredi raised the question of determining the chromatic number of the square of the Kneser graph, where thesquare of a graph is the graph obtained by adding edges joining vertices at distance at most 2. We prove that χ(K²(2k+1,k))≤4k whenk is odd and χ(K²(2k+1,k))≤4k+2 whenk is even. Also, we use intersecting families of sets to prove lower bounds on χ(K²(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.

The authors thank Z. Füredi for introducing this problem and providing helpful discussion and suggestions. The authors also thank A.V. Kostochka and D.B. West for their helpful suggestions and comments about this paper.

Authors and Affiliations

1. Department of Mathematics, University of Illinois, Urbana, IL 61801, USA

   Seog-Jin Kim & Kittikorn Nakprasit

Corresponding author

Correspondence toSeog-Jin Kim.

This work was partially supported by NSF grant DMS-0099608

Final version received: April 23, 2003

Reprints and permissions