Chromatic Numbers of Some Distance Graphs

For positive integers n > r > s, G(n, r, s) is the graph whose vertices are the r-element subsets of an n-element set, two subsets being adjacent if their intersection contains exactly s elements. We study the chromatic numbers of this family of graphs. In particular, the exact value of the chromatic number of G(n, 3, 2) is found for infinitely many n. We also improve the best known upper bounds for chromatic numbers for many values of the parameters r and s and for all sufficiently large n.