{"id":"arxiv/2610.13723","url":"https://arxiv.org/abs/2610.13723","tags":["math.CO"],"score":0,"title":"List chromatic number of $G(n,r,s)$ graphs","domain":"math.CO","source":"arxiv","authors":["M. Koshelev"],"reviews":0,"subject":"math.CO","summary":"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 $χ_L(G(n,r,s)) = Θ(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 $χ_L(G(n,r,0)) \\geq \\frac{n}{120}\\ln\\left(\\frac{en}{r}\\right)$. Together with previous results of Bulankina, Inozemtsev and Kupavskii…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-09","reactions":{}}