Chromatic numbers of graphs of intersections

D. Zakharov

Published 2018-11-06Version 1

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)$. Using 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 fixed $r, s$. Also we depelop a new elementary approach and prove that $\chi(G(n, 4, 2)) \sim \frac{n^2}{6}$ without use of Keevash's results.