Reconfiguration of List Colourings

Given a proper (list) colouring of a graph G, a recolouring step changes the colour at a single vertex to another colour (in its list) that is currently unused on its neighbours, hence maintaining a proper colouring. Suppose that each vertex v has its own private list $L(v)$ of allowed colours such that |L(v)|≥ deg(v)+1. We prove that if G is connected and its maximum degree Δ is at least $3$, then for any two proper L-colourings in which at least one vertex can be recoloured, one can be transformed to the other by a sequence of O(|V(G)|²) recolouring steps. We also show that reducing the list-size of a single vertex w to deg(w) can lead to situations where the space of proper L-colourings is `shattered'. Our results can be interpreted as showing a sharp phase transition in the Glauber dynamics of proper L-colourings of graphs. This constitutes a `local' strengthening and generalisation of a result of Feghali, Johnson, and Paulusma, which considered the situation where the lists are all identical to \1,…,Δ+1\.