List chromatic number of $G(n,r,s)$ graphs
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.13723
curl -X POST /api/v1/records/arxiv/2610.13723/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.13723/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'