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 $\mathrm{\mid }L(v)\mathrm{\mid }\ge deg(v)+1$. We prove that if $G$ is connected and its maximum degree $\mathrm{\Delta }$ 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(\mathrm{\mid }V(G){\mathrm{\mid }}^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,\dots ,\mathrm{\Delta }+1\}$.