Title: On the chromatic number of the square of the Kneser graph K(2k+1, k)


Seog-Jin Kim (speaker) and Kittikorn Nakprasit

University of Illinois at Urbana-Champaign

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.
Zoltan Furedi 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 the vertices at distance 2.

We prove that the chromatic number of the square of K(2k+1, k) is at most
4k when k is odd and the chromatic number of the square of K(2k+1, k)
is at most 4k+2 when k is even.

Also, we use intersecting families of sets to prove lower bounds on
the chromatic number of square of 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.