Paths between colourings of sparse graphs
share
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 on exactly one vertex. We give a short proof of the following theorem of Bousquet and Perarnau (European Journal of Combinatorics, 2016). Let d and k be positive integers, k ≥ d + 1. For every ϵ > 0 and every graph G with n vertices and maximum average degree d - ϵ, there exists a constant c = c(d, ϵ) such that R_k(G) has diameter O(n^c). Our proof can be transformed into a simple polynomial time algorithm that finds a path between a given pair of colourings in R_k(G).
READ FULL TEXT