Abstract:
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$.
Fulltext:
PDF file (486 kB)
