Optimally Reconfiguring List and Correspondence Colourings

The reconfiguration graph ${\mathcal{C}}_k(G)$ for the $k$-colourings of a graph $G$ has a vertex for each proper $k$-colouring of $G$, and two vertices of ${\mathcal{C}}_k(G)$ are adjacent precisely when those $k$-colourings differ on a single vertex of $G$. Much work has focused on bounding the maximum value of $\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}{\mathcal{C}}_k(G)$ over all $n$-vertex graphs $G$. We consider the analogous problems for list colourings and for correspondence colourings. We conjecture that if $L$ is a list-assignment for a graph $G$ with $|L(v)|\ge d(v)+2$forall$v\in V(G)$,then${\rm{diam}}~$\mathcal{C}$_L(G)\le n(G)+\mu(G)$\mathrm{.}Wealsoconjecturethatif$(L,H)$ is a correspondence cover for a graph $G$ with $\mathrm{\mid }L(v)\mathrm{\mid }\ge d(v)+2$ for all $v\in V(G)$, then $\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}{\mathcal{C}}_{(L,H)}(G)\le n(G)+\tau (G)$. (Here $\mu (G)$ and $\tau (G)$ denote the matching number and vertex cover number of $G$.) For every graph $G$, we give constructions showing that both conjectures are best possible. Our first main result proves the upper bounds (for the list and correspondence versions, respectively) ${\rm{diam}}~$\mathcal{C}$L(G)\le n(G)+2\mu(G)$and${\rm{diam}}~$\mathcal{C}${(L,H)}(G)\le n(G)+2\tau(G)$. Our second main result proves that both conjectured bounds hold, whenever all $v$ satisfy $\mathrm{\mid }L(v)\mathrm{\mid }\ge 2d(v)+1$. We conclude by proving one or both conjectures for various classes of graphs such as complete bipartite graphs, subcubic graphs, cactuses, and graphs with bounded maximum average degree.