The diameter of recoloring graphs under a maximum average degree bound
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(…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.32688
curl -X POST /api/v1/records/arxiv/2609.32688/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.32688/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'