Chromatic numbers of Kneser-type graphs

Let $G(n,r,s)$ be a graph whose vertices are all $r$-element subsets of an $n$-element set, in which two vertices are adjacent if they intersect in exactly $s$ elements. In this paper we study chromatic numbers of $G(n,r,s)$ with $r,s$ being fixed constants and $n$ tending to infinity. Using a recent result of Keevash on existence of designs we deduce an inequality $\chi(G(n, r, s)) \le (1+o(1))n^{r-s} \frac{(r-s-1)!}{(2r-2s-1)!}$for$r > s$with$r, s$fixedconstants\mathrm{.}Thisinequalitygivessharpupperboundsfor$r \le 2s+1$. Also we develop an elementary approach to this problem and prove that $\chi (G(n,4,2))\sim \frac{n^2}{6}$ without use of Keevash’s results. Some bounds on the list chromatic number of $G(n,r,s)$ are also obtained.