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