Publication at Faculty of Mathematics and Physics |
2021
Abstract
The reconfiguration graph R-k(G) for the k-colorings of a graph G has as vertex set the set of all possible k-colorings of G and two colorings are adjacent if they differ in the color of exactly one vertex of G. Let d, k >= 1 be integers such that k >= d + 1.
We prove that for every epsilon > 0 and every graph G with n vertices and maximum average degree d - epsilon, R-k(G) has diameter O(n(log n)(d-1)). This significantly strengthens several existing results. (c) 2020 Elsevier Inc.
All rights reserved.