List chromatic number of $G(n,r,s)$ graphs

Abstract

We study the list chromatic number of generalized Johnson graphs. Recall that the vertices of such graphs are all possible $r$-element subsets of $[n] = \{1, \dotsc, n\}$ and an edge is drawn between two vertices if and only if corresponding sets have exactly $s$ common elements. We prove that for any fixed $s \geq 1$ and $r \geq 2s + 2$ we have $\chi_L(G(n,r,s)) = \Theta(n^{s+1}\ln n)$. In case where $s = 0$ we prove that for all $4\ln n \leq r \leq n/20$ we have $\chi_L(G(n,r,0)) \geq \frac{n}{120}\ln\left\{\frac{en}{r}\right\}$. Together with previous results of Bulankina, Inozemtsev and Kupavskii this proves that $\chi_L(G(n,r,0)) = \Theta\left\{n\ln\left\{\frac{en}{r}\right\}\right\}$ uniformly for $2 \leq r \leq (1/2-\varepsilon)n$.