{"id":"arxiv/2609.32688","url":"https://arxiv.org/abs/2609.32688","tags":["math.CO"],"score":0,"title":"The diameter of recoloring graphs under a maximum average degree bound","domain":"math.CO","source":"arxiv","authors":["Ruilin Zheng","Junying Lu"],"reviews":0,"subject":"math.CO","summary":"For a graph $G$, we write $\\mathrm{mad}(G)$ for its maximum average degree and $\\mathrm{diam} G$ for its diameter. Let $R_k(G)$ be the graph whose vertices are the proper colorings of $G$ with $k$ colors, where two colorings are adjacent when they differ at one vertex. Feghali (JCTB, 2021) proved that, for fixed integers $d,k\\ge 1$ with $k\\ge d+1$ and every $\\varepsilon>0$, every $n$-vertex graph $G$ satisfying $\\mathrm{mad}(G)\\le d-\\varepsilon$ has $\\mathrm{diam} R_k(G)=O_{d,k,\\varepsilon}(n(\\log n)^{d-1})$. In this article, we prove that \\[ \\mathrm{diam} R_k(G)=O_{d,k,\\varepsilon}\\!\\left(…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-26","reactions":{}}