Reconfiguring colourings of graphs with bounded maximum average degree
The reconfiguration graph R_k(G) of the k-colourings of a graph G has as vertex set the set of all possible k-colourings of G and two colourings are adjacent if they differ in exactly one vertex of G. Let d, k ≥ 1 such that k ≥ d+1. We prove that for every ϵ > 0 and every graph G with n vertices and maximum average degree d - ϵ, R_k(G) has diameter O(n( n)^d).
READ FULL TEXT