PreprintCC BY 4.0arXiv
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 ≥ 1 and r ≥ 2s + 2 we have χL(G(n,r,s)) = Θ(ns+1ln n). In case where s = 0 we prove that for all 4ln n ≤ r ≤ n/20 we have χL(G(n,r,0)) ≥ n/120ln(en/r). Together with previous results of Bulankina, Inozemtsev and Kupavskii this proves that χL(G(n,r,0)) = Θ(nln(en/r)) uniformly for 2 ≤ r ≤ (1/2−ε)n.
Related
BibTeX
@misc{koshelev2026list,
title = {{List chromatic number of $G(n,r,s)$ graphs}},
author = {M. Koshelev},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.13723},
eprint = {2610.13723},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.13723},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - List chromatic number of G(n,r,s) graphs
AU - M. Koshelev
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2610.13723
UR - https://arxiv.org/abs/2610.13723
AB - 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 ≥ 1 and r ≥ 2s + 2 we have χ_L(G(n,r,s)) = Θ(n^s+1ln n). In case where s = 0 we prove that for all 4ln n ≤ r ≤ n/20 we have χ_L(G(n,r,0)) ≥ n/120ln(en/r). Together with previous results of Bulankina, Inozemtsev and Kupavskii this proves that χ_L(G(n,r,0)) = Θ(nln(en/r)) uniformly for 2 ≤ r ≤ (1/2−ε)n.
ER -