The diameter of recoloring graphs under a maximum average degree bound
Abstract
For a graph G, we write mad(G) for its maximum average degree and diam G for its diameter. Let Rk(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≥ 1 with k≥ d+1 and every ε>0, every n-vertex graph G satisfying mad(G)≤ d−ε has diam Rk(G)=Od,k,ε(n(log n)d−1). In this article, we prove that diam Rk(G)=Od,k,ε ( n(log n)⌊ (d−1)/(k−d)⌋ ), which extends the result proved by Feghali directly. The proof uses a partition into independent layers and removes k−d colors at each recursive stage. We also improve the bound on the number of layers and determine the best possible linear coefficient in the forest case. More precisely, for 0<ε<2, every n-vertex graph G with mad(G)≤2−ε satisfies diam R3(G)≤ρM n, where M=⌊2/ε⌋, ρM=max1≤ m≤ MDm/m, and Dm is the largest diameter of R3(T) over all trees T on m vertices. Moreover, the coefficient ρM is best possible.
Related
- Proper conflict-free degree-choosability of graphs with maximum average degree less than 8/3
- The asymptotic maximum oriented diameter of graphs
- Maximum number of spanning trees in bipartite graphs with a given diameter
- Local versus global average degree in bipartite graphs
- Tuza's Conjecture for Graphs of Maximum Degree at Most 10
BibTeX
@misc{zheng2026diameter,
title = {{The diameter of recoloring graphs under a maximum average degree bound}},
author = {Ruilin Zheng and Junying Lu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.32688},
eprint = {2609.32688},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.32688},
}
RIS
TY - UNPB
TI - The diameter of recoloring graphs under a maximum average degree bound
AU - Ruilin Zheng
AU - Junying Lu
PY - 2026
DA - 2026/09/26
PB - arXiv
DO - 10.48550/arxiv.2609.32688
UR - https://arxiv.org/abs/2609.32688
AB - For a graph G, we write mad(G) for its maximum average degree and 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≥ 1 with k≥ d+1 and every ε>0, every n-vertex graph G satisfying mad(G)≤ d−ε has diam R_k(G)=O_d,k,ε(n(log n)^d−1). In this article, we prove that diam R_k(G)=O_d,k,ε ( n(log n)^⌊ (d−1)/(k−d)⌋ ), which extends the result proved by Feghali directly. The proof uses a partition into independent layers and removes k−d colors at each recursive stage. We also improve the bound on the number of layers and determine the best possible linear coefficient in the forest case. More precisely, for 0<ε<2, every n-vertex graph G with mad(G)≤2−ε satisfies diam R_3(G)≤ρ_M n, where M=⌊2/ε⌋, ρ_M=max_1≤ m≤ MD_m/m, and D_m is the largest diameter of R_3(T) over all trees T on m vertices. Moreover, the coefficient ρ_M is best possible.
ER -