Total: 1
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)|2) 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}.