Reconfiguration of List Colourings Stijn Cambie, Wouter Cames van Batenburg, Daniel W. Cranston, Ross J. Kang Abstract Given a proper (list) colouring of a graph G 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 v has its own private list L ⁡ ( v ) L(v) of allowed colours such that | L ⁡ ( v ) | ≥ deg ⁡ ( v ) + 1 |L(v)|\geq\deg(v)+1 . We prove that if G G is connected and its maximum degree Δ \Delta is at least 3 3 , then for any two proper L 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 ) O(|V(G)|^{2}) recolouring steps. We also show that reducing the list-size of a single vertex w w to deg ⁡ ( w ) \deg(w) can lead to situations where the space of proper L L -colourings is ‘shattered’. Our results can be interpreted as showing a sharp phase transition in the Glauber dynamics of proper L 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 } \{1,\ldots,\Delta+1\} . Deptartment of Mathematics, London School of Economics & Political Science, London, UK. Email: j.van-den-heuvel@lse.ac.uk . 1 Introduction One of the most basic results in graph theory is that the vertices of a graph G can be properly coloured with at most \Delta+1 colours, where \Delta is the maximum degree of G . This remains true if instead we provide every vertex v with a private list L(v) of at least \deg(v)+1 colours to choose from (where \deg(v) denotes the number of neighbours of v ). This means that the collection of proper colourings is non-empty. What does this collection look like? We are especially interested in how ‘closely linked’ its colourings are to each other. For the situation above, we show that a vast majority of all colourings are connected, in a precise way that we will discuss below. Connectedness of all colourings implies that a widely-studied Markov chain known as the Glauber dynamics of (list) colourings is ergodic. Our results demonstrate a fine balance essentially at the boundary of ergodicity; increasing or decreasing the number of available colours by one at even a single vertex changes the guaranteed component structure dramatically. To state our main results, we need some basic definitions. Given a graph G , a list-assignment L is an assignment of lists of colours L(v)\subseteq\mathbb{N} to each vertex v of G . A proper L -colouring is a proper colouring \gamma:V(G)\rightarrow\mathbb{N} such that \gamma(v)\in L(v) for every v\in V(G) . (We often omit the adjective ‘proper’ when this does not lead to confusion.) A (single vertex) recolouring of a proper L -colouring \gamma changes the colour under \gamma of one vertex v to another colour of L(v) , such that the resulting colouring is again proper. Such a recolouring is only possible if the new colour is not already used by \gamma on any of the neighbours of v . A recolouring sequence is a sequence of single vertex recolourings. If no vertex of G can be recoloured from \gamma , we call \gamma frozen ; otherwise it is unfrozen . Given a graph G and list-assignment L , the list colouring reconfiguration graph \mathcal{C}(G,L) has as vertices all proper L -colourings of G , and two L -colourings are adjacent if one can be obtained from the other by recolouring a single vertex. The frozen L -colourings form singletons in \mathcal{C}(G,L) (components with just one vertex). As our main focus is on the recolouring components of L -colourings, we may restrict our attention to the unfrozen L -colourings, and thus to the subgraph \widehat{\mathcal{C}}(G,L) of \mathcal{C}(G,L) induced by such colourings. If for all v\in V(G) we have L(v)=\{1,\ldots,k\} for some positive integer k , then we write \mathcal{C}(G,k) and \widehat{\mathcal{C}}(G,k) . Main Results . Let G be a connected graph with n vertices, and let L be a list-assignment of G . 1. ( Key Lemma ) If |L(v)|\geq\deg(v)+1 for all v\in V(G) and |L(w)|\geq\deg(w)+2 for at least one w\in V(G) , then \mathcal{C}(G,L) is connected and has diameter O(n^{2}) . 2. ( Main Theorem ) If L|(v)|\geq\deg(v)+1 for all v\in V(G) and G has maximum degree \Delta\geq 3 , then \widehat{\mathcal{C}}(G,L) is connected and has diameter O(n^{2}) . Moreover, if \Delta=o(n^{1/4}) , then the number of frozen L -colourings is vanishingly small compared to the number of unfrozen ones. 3. ( Shattering Observation ) If |L(w)|=\deg(w) for some w\in V(G) and |L(v)|\geq\deg(v)+1 for all other v\in V(G) , then the number of components in \widehat{\mathcal{C}}(G,L) can be exponential (in terms of n ). These results align with several active research areas in graph theory, theoretical computer science, and statistical physics. Before going into details about those connections, we give a few observations about the results above. The condition that G is connected is essential in the Key Lemma, as otherwise we can have L -colourings that are frozen in some components of G (and hence can’t be recoloured on those vertices), but unfrozen in other components. The condition that the maximum degree is at least 3 in the Main Theorem is necessary. For instance, the thirty 3 -colourings of the cycle C_{5} are all unfrozen, but \mathcal{C}(C_{5},3) has two connected components with fifteen 3 -colourings each. In fact, all cycles of length at least 5 and paths of length at least 6 show similar behaviour; for more on this, see Subsection 4.1 . The two diameter bounds are sharp up to a multiplicative constant, even when G is restricted to being a tree. This is the case as any subpath of degree- 2 vertices of length \Omega(n) is enough to ensure that \widehat{\mathcal{C}}(G,L) has \Omega(n^{2}) diameter. We remark here that a subset of the authors [ 7 ] showed that with lists of size \deg(v)+2 for each vertex v , the diameter of \mathcal{C}(G,L) is at most 2n . In the final section, we discuss further conditions that could strengthen our results. In ‘classical’ chromatic graph theory we are typically interested in sharp conditions that ensure that G is k -colourable; i.e., that \mathcal{C}(G,k) is non-empty. As mentioned above, a basic example is the condition k\geq\Delta+1 , which is sharp when G is a clique or an odd cycle. By Brook’s Theorem [ 6 ] , these are the only cases for connected G where we actually need \Delta+1 colours. Arguably, ‘classical’ graph colouring reconfiguration theory has followed a similar path, through a focus instead on sharp conditions that ensure that \mathcal{C}(G,k) is connected. Jerrum [ 24 ] showed that \mathcal{C}(G,k) is connected whenever k\geq\Delta+2 . This result follows from a simple inductive proof, as we elaborate upon later. By contrast, there exists a connected G with a (\Delta+1) -colouring that admits no recolouring step; and then, by permutation of the colours, \mathcal{C}(G,\Delta+1) must contain at least (\Delta+1)! singleton components. The simplest examples are cliques and cycles with length divisible by 3 , but there are many others, e.g. the 3 -cube Q_{3} . More generally, take any (\Delta+1) -partite graph in which each vertex has exactly one neighbour in each part, but its own; when we use the same colour on all vertices in each part, no recolouring step is possible. For connected G , is having a frozen (\Delta+1) -colouring also a necessary condition for \mathcal{C}(G,\Delta+1) to be disconnected? Feghali, Johnson, and Paulusma [ 19 ] showed that this is indeed the case, and in an even stronger sense as follows. Theorem 1 (Feghali, Johnson, and Paulusma [ 19 ] ) . If G is a connected graph with n vertices and maximum degree \Delta\geq 3 , then \widehat{\mathcal{C}}(G,\Delta+1) is connected and has diameter O(n^{2}) . Determining whether an arbitrary connected \Delta -regular G has a frozen (\Delta+1) -colouring appears to be non-trivial. However, this characterisation for disconnectedness of \mathcal{C}(G,\Delta+1) given in Theorem 1 can be viewed as a reconfiguration parallel to Brooks’ simple characterisation for emptiness of \mathcal{C}(G,\Delta) . The diameter bound of O(n^{2}) was recently improved by Bousquet, Feuilloley, Heinrich, and Rabie [ 5 ] to O(n) (albeit with a leading constant factor that hides a superexponential dependency upon \Delta ). As mentioned earlier, a subset of the present authors [ 7 ] recently showed a 2n bound on the diameter of \mathcal{C}(G,\Delta+2) (improving considerably on the bound implicit in Jerrum’s original argument), and conjectured a 1.5n diameter bound. Our work draws the same parallel, but in the refined setting where each vertex gets a private or ‘local’ list of colours. Colouring greedily shows the following. If G is connected and L is a list-assignment such that |L(v)|\geq\deg(v) for all v\in V(G) and |L(w)|\geq\deg(w)+1 for at least one w\in V(G) , then G has an L -colouring. The Key Lemma constitutes a reconfiguration parallel of this observation. Furthermore, a classic result independently due to Borodin [ 4 ] and Erdős, Rubin, and Taylor [ 16 ] states that if G is connected and L is a list-assignment such that |L(v)|\geq\deg(v) for all v\in V(G) , then G has an L -colouring unless G has a specific structure (a mild generalisation of a tree called a Gallai tree ) together with a specific list-assignment L . The Main Theorem constitutes a reconfiguration parallel of this ‘local’ Brooks’-type characterisation. Following on the work in [ 4 , 16 ] , there has been extensive research in chromatic graph theory for this notion of ‘local’ colouring: for triangle-free graphs [ 3 , 14 ] , Reed’s Conjecture [ 12 , 27 ] , disjoint list colourings [ 8 ] , and fractional colourings [ 26 ] , to name a few examples. One inspiration for research on recolouring graphs comes from the theory of approximate counting, which has deep links via randomised algorithms to statistical physics. A unifying topic is the Glauber dynamics for proper colourings of a graph. In physical applications, the graph usually assumes a lattice structure, we consider the colours as spins in the system, and take an idealised extreme temperature regime, so that no two neighbouring vertices (sites in the lattice crystal) may share the same colour (spin). In the Glauber dynamics of proper k -colourings of a graph G , at each step some vertex v\in V(G) and some colour c\in\{1,\ldots,k\} are chosen uniformly at random. If v can be recoloured with colour c such that the colouring remains proper, then the Markov chain takes this colouring as its new state; otherwise it remains unchanged. As mentioned earlier, Jerrum [ 24 ] noticed that if k\geq\Delta+2 , then the state space of this chain is connected. Since this chain is also aperiodic and symmetric, it converges to an equilibrium that equals the uniform distribution over all proper k -colourings, by the ergodic theorem; see [ 25 ] . This probability distribution is an important global parameter of the system, since it is equivalent to the number of proper k -colourings. Jerrum [ 24 ] moreover conjectured that this process converges rapidly (within a number of steps polylogarithmic in the number of states) to equilibrium, which would imply an efficient randomised approximation scheme for estimating the number of proper (\Delta+2) -colourings; [ 21 ] provides wider context. Importantly, Jerrum [ 24 ] (see also [ 29 ] ) further showed this conjecture to be true up to a constant factor increase in k . Significant effort has gone towards reducing the constant factor [ 9 , 10 , 30 ] , even if proving rapid mixing for all k\geq\Delta+2 still seems far out of reach. Theorem 1 may be interpreted as follows. For connected G , if k\geq\Delta+1 , then the Glauber dynamics of proper k -colourings is ergodic, provided the chain is restricted to the unfrozen colourings. Bonamy, Bousquet, and Perarnau [ 2 ] showed moreover that the frozen colourings constitute a vanishingly small proportion of all proper k -colourings. This means that, provided we check that the initial colouring is unfrozen (which is the case nearly always), the Glauber dynamics converges to an almost uniform sample from the space of proper k -colourings. Note that the additional assertion in our Main Theorem is a partial strengthening of this result of Bonamy et al. Furthermore, the fact that the diameter of the unfrozen part of the state space is O(n) [ 5 ] lends credence to the idea that the rapid mixing conjecture might still hold with \Delta+1 colours, provided we restrict to the unfrozen colourings. Note that Bonamy et al. [ 2 ] have also shown that the mixing time for this problem is \Omega(n^{2}) . For the obvious generalisation of the Glauber dynamics to list colourings, at each step a vertex v and a colour c\in L(v) are chosen uniformly at random. Again, the Markov chain takes the new colouring as its new state as long as it is proper; otherwise it remains unchanged. Our Main Results may be viewed in terms of the Glauber dynamics of proper L -colourings of some connected G , provided the list-size conditions for L(v) are \deg(v)+1 for all vertices v except possibly for one. Our Main Theorem says that the Glauber dynamics on unfrozen L -colourings is ergodic provided all of the list-sizes are at least \deg(v)+1 for all vertices v and the maximum degree \Delta is at least 3 ; and the rest of the state space is negligible if \Delta is not too large. Our Key Lemma says that there are no frozen L -colourings if in addition we require one of the vertices to have a strictly larger list-size. Our Shattering Observation demonstrates that if even merely one vertex v has a smaller list-size of \deg(v) , then the state space may fracture into many disconnected pieces. In such a situation, a more ‘global’ dynamics — one that can recolour more than one vertex at a time — is necessary to approximately uniformly sample from the proper L -colourings. To underscore the ‘local’ perspective we have adopted in this work, specific to the Glauber dynamics of colourings, we propose the following strengthening of the rapid mixing conjecture. Conjecture 2 . Let G be a connected graph, and let L be a list-assignment of G . If |L(v)|\geq\deg(v)+2 for all v\in V(G) , then the Glauber dynamics for proper L -colourings of G mixes rapidly. In a sense, this conjecture has already been considered in the (randomised) algorithms community. More specifically, many of the approaches towards the uniform version of the conjecture [ 9 , 10 , 30 ] also seem to yield local analogues. Moreover, Chen, Liu, Manu, and Moitra [ 11 ] have shown that Conjecture 2 holds when the lists are just slightly larger, of size \deg(v)+3 for each vertex v , and G has sufficiently large girth. Indeed, local colouring has arisen in various algorithmic contexts (and naturally so, given how efficient colouring algorithms are often based upon local arguments), not just in approximate counting [ 11 , 22 ] , but also in distributed computing [ 13 , 17 , 23 ] and graph sparsification [ 1 , 20 ] , for instance. 1.1 Proof Ideas In this subsection we outline some of the key ideas used to prove our results. Remark . In the remainder of the paper, unless otherwise stated, we assume that all graphs encountered are connected and all (list) colourings are proper. Given a list-assignment L of a graph G and an L -colouring \gamma , we say that a vertex v is frozen under \gamma if v cannot be recoloured (i.e., if all colours in L(v)\setminus\{\gamma(v)\} appear among the neighbours of v ); otherwise it is unfrozen . Following the earlier definition, this means a colouring \gamma is frozen if all vertices are frozen under \gamma , and \gamma is unfrozen if at least one vertex is unfrozen. Informally, an unfrozen vertex remains unfrozen when we restrict a list-assignment to an induced subgraph containing it. We formalize this intuition in the following observation, which we use frequently and implicitly throughout the rest of the paper. Observation 3 . Let G be a graph with a list-assignment L , and let \alpha be an L -colouring of G . Given a set of vertices W\subseteq V(G) , we form a list-assignment L_{W} for G[W] from L by removing the colours of the neighbours, i.e., L_{W}(v):=L(v)\setminus\bigcup_{w\in N_{G}(v)\setminus W}\alpha(w) for all v\in W . Let \alpha_{W} denote the L_{W} -colouring formed by restricting \alpha to G[W] . Fix x,y\in W . If y is unfrozen under \alpha then it is unfrozen under \alpha_{W} . Moreover, if \alpha_{W} can be recoloured to an L_{W} -colouring of G[W] such that both x and y are unfrozen, then the same recolouring sequence (lifted to G ) recolours \alpha to an L -colouring of G such that x and y are unfrozen. Proof. If y is unfrozen under \alpha , then some colour c\in L(y) is unused by \alpha on N_{G}[y] . Therefore c\in L_{W}(y) , so y is unfrozen under \alpha_{W} . For the second statement, note that every L_{W} -colouring of G[W] is also an L -colouring of G[W] , and every vertex that is unfrozen under some L_{W} -colouring \gamma of G[W] is also unfrozen under the L -colouring of G formed by the union of \gamma and \alpha|_{V(G)-W} . ∎ Most of our arguments do not use the actual contents of the lists in a given list-assignment, but only the size of the lists, and in particular how much larger a particular list L(v) is compared to the degree of the vertex v . To help describe this more compactly, given some non-negative integer t and a list-assignment L , we say that a vertex v has a +t -list (with respect to L ) if |L(v)|\geq\deg(v)+t , and that L is a +t -list-assignment if every vertex in G has a +t -list. We motivate our methodology by describing a useful step towards understanding the characterisation for degree-choosability mentioned earlier (see [ 4 , 16 ] ). That is, for which graphs G is there always guaranteed to be an L -colouring for any given +0 -list-assignment L of G ? We can easily prove that if L is instead a +0 -list-assignment of G such that some v\in V(G) has a +1 -list, then \mathcal{C}(G,L) is non-empty. This is by induction on the number of vertices. If L_{-v} denotes the restriction of L to G-v , then note that any neighbour of v has a +1 -list with respect to L_{-v} . In particular, for any component of G-v , L_{-v} is a +0 -list-assignment in which at least one vertex has a +1 -list. Thus, by the inductive hypothesis, \mathcal{C}(G-v,L_{-v}) is non-empty. Since v has a +1 -list with respect to L , any element of \mathcal{C}(G-v,L_{-v}) can be extended by colouring v with an available colour from L(v) to an L -colouring of G , completing the induction. Along the same parallel we proposed earlier on page 1 , we can obtain with the same idea a weaker form of the Key Lemma, one where we are not concerned by a bound on the diameter. Again this is by induction on the number of vertices. Suppose that L is a +1 -list-assignment of G such that some vertex v has a +2 -list. If L_{-v} denotes the restriction of L to G-v , then note that any neighbour u of v has a +2 -list with respect to L_{-v} . In particular, for any component of G-v , L_{-v} is a +1 -list-assignment in which at least one vertex has a +2 -list. Thus, by the inductive hypothesis applied on each component, \mathcal{C}(G-v,L_{-v}) is connected. Now let \alpha and \beta be two elements of \mathcal{C}(G,L) . By the arguments above, their restrictions \alpha_{-v} and \beta_{-v} to G-v are connected in \mathcal{C}(G-v,L_{-v}) by an L_{-v} -recolouring sequence. We essentially ‘extend’ this to an L -recolouring sequence between \alpha and \beta , except that we often may have to recolour v to another available colour in L(v) to avoid some conflict on one of its neighbours before taking the next step in the L_{-v} -recolouring sequence. This is always possible because v has a +2 -list with respect to L . This argument yields a bound on \diam(\mathcal{C}(G,L)) that is exponential in |V(G)| . Obtaining a quadratic bound requires considerably more care, and will be done in the next section. Key Lemma, precise version . Let G be a connected graph with n vertices, and let L be a list-assignment of G . If |L(v)|\geq\deg(v)+1 for all v\in V(G) and |L(w)|\geq\deg(w)+2 for at least one w\in V(G) , then \mathcal{C}(G,L) is connected and has diameter at most \tfrac{1}{2}(3n^{2}+5n) . If G is 2 -connected but does not have all lists identical, then our Main Theorem essentially follows from our Key Lemma. We find neighbours v,w with L(v)\not\subseteq L(w) , colour v from L(v)\setminus L(w) , and apply the Key Lemma to G-v . If G has cut-vertices, then we recolour one ‘outermost’ block (a leaf in the block tree) from \alpha to \beta , and finish by induction on the number of blocks. This brings us to the following. An important special case of our Main Theorem is when G is 2 -connected and regular and L(v)=\{1,\ldots,\Delta+1\} for all v . (This is the 2 -connected case in the main result of Feghali et al. [ 18 ] .) In his elegant proof of Brooks’ Theorem, Lovász [ 28 ] proved the following easy lemma: If G is 2 -connected with minimum degree at least 3 , then there exist v,w_{1},w_{2}\in V(G) with w_{1},w_{2}\in N(v) and w_{1}w_{2}\notin E(G) such that G-\{w_{1},w_{2}\} is connected. To prove Brooks’ Theorem, assign the same colour to w_{1} and w_{2} , then colour greedily inward along a spanning tree T in G-\{w_{1},w_{2}\} rooted at v . To handle the special case above, we elaborate on this idea. First, we show that from every unfrozen (\Delta+1) -colouring we can get to one that uses a common colour c_{1} on some w_{1},w_{2} as above. Second, we show that we can ‘transfer’ from the class of (\Delta+1) -colourings that use c_{1} on w_{1},w_{2} (neighbours of w ), which are reachable from \alpha , to the class of (\Delta+1) -colourings that use some c_{1}^{\prime} on w_{1}^{\prime},w_{2}^{\prime} (neighbours of some w^{\prime} ), which are reachable from \beta . To effect this transfer, we construct a colouring that lies in both classes. Our proof of the Main Theorem is self-contained. So, in particular, it provides an alternative proof of the main result of Feghali et al. [ 19 ] . In fact, if we aim only to recover that the recolouring diameter of \widehat{\mathcal{C}}(G,\Delta+1) is O(|V(G)|^{2}) , then we can significantly streamline the proof, essentially needing only the contents of Sections 2 and 3 , as well as Claims 2 and 3 in the proof of Theorem 23 . We also point out that even when all lists have size \Delta(G)+1 , which is equivalent to the case when G is \Delta -regular, our Main Theorem is a new result. 1.2 Organisation The remainder of the paper is organised as follows. In the next section, we prove the precise form of the Key Lemma. Section 3 deals with the special case that G is a 2 -connected regular graph in which all lists are identical. The Main Theorem is proved in Section 4 . That section starts with a tedious but necessary analysis of some simple cases, including paths and cycles. Although paths and cycles do not satisfy the condition in the Main Theorem that the maximum degree is at least 3, we may encounter them when ‘breaking down’ the block tree of graphs with connectivity 1 . Finally, in Section 5 we describe the examples for the Shattering Observation, pose some questions, and discuss possible directions for future research. In particular, we discuss extending our results to correspondence colourings , which appears surprisingly non-straightforward. 2 Proof of the Key Lemma Let G be a connected graph, and let L be a +1 -list-assignment of G with some v\in V(G) where |L(v)|\geq\deg(v)+2 . The next three lemmas allow us to recolour from an arbitrary L -colouring to one where a given vertex w uses any specified colour \beta(w) in its list; applying this repeatedly yields the Key Lemma. The first lemma allows us to ‘push’ unfrozenness from one vertex v to another vertex w along a shortest v,w -path. The second lemma allows us to recolour so that either w uses \beta(w) , or else \beta(w) is used on a single neighbour x of w and both w and x are frozen. The third lemma allows us to unfreeze w or x to move past the possible ‘bad’ outcome of the second lemma, and ultimately recolour w with \beta(w) . Lemma 4 . Let G be a connected graph, L be a +1 -list-assignment for G , and \alpha be an L -colouring. Fix v,w\in V(G) , let d:=\textrm{dist}(v,w) , and let P be a shortest v,w -path. If v is unfrozen in \alpha , then there exists a recolouring sequence \mathcal{S} from \alpha to some L -colouring \gamma such that (i) w is unfrozen under \gamma , (ii) every vertex that is recoloured during \mathcal{S} belongs to V(P)\setminus\{w\} , and (iii) |\mathcal{S}|\leq d . Moreover, note that if |L(v)|\geq\deg(v)+2 , then v is also unfrozen under \gamma . Proof. Let P=v_{0}\cdots v_{d} , with v_{0}=v and v_{d}=w . Let i be the largest index with v_{i} unfrozen; i exists, since v_{0} is unfrozen. Recolouring v_{i} unfreezes v_{i+1} , and we finish by induction on d-i . ∎ Lemma 5 . Let G be a connected graph, and let L be a +1 -list-assignment for G . Let \alpha,\beta be two unfrozen L -colourings. For each vertex w , there exists a recolouring sequence \mathcal{S} from \alpha to some L -colouring \gamma such that (i) either \gamma(w)=\beta(w) , or there is precisely one vertex x\in N(w) with \gamma(x)=\beta(w) and w and x are frozen, and (ii) |\mathcal{S}|\leq\deg(w)+2 , with equality only if \gamma(w)=\beta(w) . Proof. Given \alpha and w , a bad neighbour is any neighbour of w coloured \beta(w) . We assume that \alpha(w)\neq\beta(w) and that w has at least one bad neighbour under \alpha ; otherwise we recolour w , if needed, and are done. Let B_{1} denote the set of unfrozen bad neighbours, and B_{2} the set of frozen bad neighbours. We first recolour each bad neighbour in B_{1} . Note that B_{1}\cup B_{2} forms an independent set, so it cannot occur that recolouring some bad neighbour freezes another bad neighbour. Next we recolour w , if possible, which unfreezes all vertices in B_{2} . (In particular this is possible if |B_{2}|\geq 2 , because fewer than \deg(w) distinct colours are used by \alpha on N(w) .) Now we recolour each bad neighbour in B_{2} . Finally, we recolour w with \beta(w) . This process succeeds in recolouring w with \beta(w) unless w has a single bad neighbour x\in B_{2} , and both w and x are frozen. Note that each neighbour of w is recoloured at most once, and w is recoloured at most twice (and twice only if \gamma(w)=\beta(w) ), so |\mathcal{S}|\leq\deg(w)+2 , and the lemma holds. ∎ Lemma 6 . Let G be a connected graph, and let L be a +1 -list-assignment for G such that |L(v)|\geq\deg(v)+2 for some vertex v . Let \alpha,\beta be two unfrozen L -colourings. Fix w\in V(G) , and let P be a shortest v,w -path. There exists a recolouring sequence \mathcal{S} from \alpha to some L -colouring \gamma such that (i) \gamma(w)=\beta(w) , (ii) v is unfrozen under \gamma , (iii) every vertex that is recoloured during \mathcal{S} belongs to V(P)\cup(N(w)\cap\alpha^{-1}(\beta(w)) , and (iv) |\mathcal{S}|\leq\deg(w)+2+2|V(P)| . Proof. We first apply Lemma 5 , transforming \alpha to an L -colouring \gamma . If \gamma(w)=\beta(w) , then we are done. Otherwise, we assume that w has a unique bad neighbour x , and that w and x are both frozen. Our general plan is to recolour along P to unfreeze w and then recolour w and x as desired; but the details are a bit more complicated. Let w^{\prime} be the neighbour of w on P . First suppose that x lies on P ; that is, x is the penultimate vertex of P . We recolour from w along P to unfreeze x , recolour x , and recolour w with \beta(w) . So assume x is not on P (and cannot be substituted for the penultimate vertex of P to get another shortest v,w -path). Instead suppose that x is adjacent to w^{\prime} . Again, we recolour from w along P to unfreeze x , by recolouring w^{\prime} . Afterwards, we recolour x and recolour w with \beta(w) . Finally, assume that x has no neighbours on P , except for w . We recolour from v along P to unfreeze w , recolour w , and recolour x . If \beta(w) is now available for w , then we use it there and are done. But possibly \beta(w) is now used on w^{\prime} , the neighbour of w on P ; so assume this is the case. If w^{\prime} is unfrozen, then recolour w^{\prime} and afterward recolour w with \beta(w) . Otherwise, first recolour from v along P to unfreeze w^{\prime} ; thereafter, we finish as in the previous sentence. It is straightforward to check that (iv) holds. ∎ Corollary 7 . The Key Lemma, precise version, holds. Proof. Fix a connected graph G , a +1 -list-assignment L such that |L(v)|\geq\deg(v)+2 for some v , and unfrozen L -colourings \alpha,\beta . To recolour \alpha to \beta , we use induction on |V(G)| . Let T be a spanning tree rooted at v , with a leaf w . By Lemma 6 , we can recolour \alpha to an L -colouring \gamma with \gamma(w)=\beta(w) . Let G^{\prime}:=G-w , L^{\prime}(x):=L(x)\setminus\{\beta(w)\} for all x\in N(w) , and L^{\prime}(x):=L(x) otherwise. Let \alpha^{\prime} and \beta^{\prime} denote the restrictions to G^{\prime} of \alpha and \beta . By hypothesis, we can recolour \alpha^{\prime} to \beta^{\prime} . Along with the steps above, this recolours \alpha to \beta . Now, in addition, let T be a breadth first tree rooted at v . Let w_{1},\ldots,w_{n} denote the vertices of G in order of non-increasing distance from v , with w_{n}=v . Let G_{i} be formed from G by deleting w_{1},\ldots,w_{i-1} , and let \mathcal{S}_{i} denote the sequence in G_{i} to recolour w_{i} with \beta(w_{i}) . Let \mathcal{S}:=\mathcal{S}_{1}\cdots\mathcal{S}_{n} , a concatenation of sequences. Now |\mathcal{S}|=\sum_{i=1}^{n}|\mathcal{S}_{i}|\leq\sum_{i=1}^{n}(\deg_{G_{i}}(w_{i})+2+2|V(P_{i})|)\leq|E(G)|+2n+2\sum_{i=1}^{n}i=|E(G)|+2n+n(n+1)\leq\tfrac{1}{2}(3n^{2}+5n) . ∎ Using a more refined version of the arguments in this section, we can prove the following quantitatively stronger version of the Key Lemma (when the minimum degree is at least 3 ). Lemma 8 . There exists a constant C such that the following holds. Let G be a connected graph with minimum degree at least 3 and with average degree \overline{d} . If L is a +1 -list-assignment for G such that |L(x)|\geq\deg(x)+2 for some x\in V(G) , then \diam\mathcal{C}(G,L)\leq C\overline{d}|V(G)| . Here we sketch the proof of Lemma 8 , which goes in three stages. The first stage is a technical variant of Lemma 6 that allows v to be any unfrozen vertex of degree at least 3 , but in return requires w to be at distance 5 or more from v . Starting from a colouring with v unfrozen, this stage produces a colouring in which v is still unfrozen and w gets colour \beta(w) . It requires at most 2|P|+\deg(w)+20 recolourings of vertices in P\cup N(w)\cup N(v) , where P is a shortest v,w -path. In the second stage we simultaneously unfreeze all vertices of a maximal set of vertices X that are pairwise at distance at least 10 . We also require that X includes the special vertex x with |L(x)|\geq\deg(x)+2 . Note that every vertex must be at distance no more than 10 from X . In the third stage we iteratively apply the technical variant to a vertex v\in X and some other vertex w at some distance d from v , where d is small (say d<30 ) but not too small ( d\geq 5 ). The technical variant ensures that w is recoloured to its target colour while keeping X\setminus\{w\} unfrozen; it requires at most 2\cdot 30+\deg(w)+20 recolouring steps. We can then finish by induction on G-w . Note however that we must carefully choose the order in which the vertices w are removed; otherwise, removing some w from G could disconnect the graph or create a vertex whose distance to X is too large. At the end, only vertices at small distance (less than 5 ) from the special vertex x remain. So we can finish by iteratively applying Lemma 6 itself, recolouring vertices working inward from the leaves of a breadth first tree rooted at u . This argument in fact yields \diam\mathcal{C}(G,L)\leq(c+\tfrac{1}{2}\overline{d})|V(G)| , for some constant c>0 . We have omitted the details of this proof, since it is technical and we have not proved that even \diam\mathcal{C}(G,L)=o(|V(G)|^{2}) . Nonetheless, it is natural to ask whether one can prove a still stronger bound in the Key Lemma: \diam\mathcal{C}(G,L)\leq C|V(G)| when the minimum degree is at least 3 , removing the dependence on \overline{d} . 3 Regular Graphs with Identical Lists In this section, we prove the Main Theorem in the special case that G is a 2 -connected regular graph and all lists are identical. This implies the main result of Feghali et al. [ 18 ] in the case when G is 2 -connected. It is also a crucial step in our proof of the Main Theorem. Remark . Henceforth, for brevity whenever a graph G has a +1 -list-assignment L we will assume that |L(v)|=\deg(v)+1 for all v\in V(G) . Otherwise, we are done by the Key Lemma. Definition 9 . For a graph G , a list-assignment L for V(G) , and L -colourings \alpha and \beta , we write \alpha\sim_{L}\beta to denote that we can recolour \alpha to \beta by a sequence of single vertex recolourings, at each step maintaining an L -colouring. When L is clear from context, we will often simply write \alpha\sim\beta . Observation 10 . Fix a connected graph G and a +1 -list-assignment L . To show that \alpha\sim\beta for given unfrozen L -colourings \alpha and \beta , it suffices to specify arbitrary vertices v,w and handle the case that v is unfrozen in \alpha and w is unfrozen in \beta . Proof. Since \alpha is unfrozen, it has some vertex z that is unfrozen; pick such a z that is nearest to v . Now recolour along a shortest path from z to v to unfreeze v ; call the resulting L -colouring \alpha^{\prime} . Clearly \alpha\sim\alpha^{\prime} . Similarly, there exists an L -colouring \beta^{\prime} with \beta^{\prime}\sim\beta and in which w is unfrozen. If we can show that \alpha^{\prime}\sim\beta^{\prime} , then we have \alpha\sim\alpha^{\prime}\sim\beta^{\prime}\sim\beta , as desired. ∎ When aiming to prove that \alpha\sim\beta , a helpful idea is to recolour \alpha to use a common colour c on two neighbours w_{1},w_{2} of some vertex v , and let G^{\prime}:=G-\{w_{1},w_{2}\} . If G^{\prime} is connected, then we can recolour it arbitrarily (except for using c on N(w_{1})\cup N(w_{2}) ), by applying the Key Lemma to v in G^{\prime} . This approach motivates our next set of definitions. Definition 11 . Let G be a connected graph, \alpha a (list) colouring of G , and v\in V(G) . A good pair for v w.r.t. \alpha is a pair of vertices w_{1},w_{2}\in N(v) such that \alpha(w_{1})=\alpha(w_{2}) ; in particular, w_{1}w_{2}\notin E(G) . A very good pair is a good pair such that G-\{w_{1},w_{2}\} is connected. If \alpha is a (\Delta+1) -colouring, \deg(v)=\Delta , and v is unfrozen in \alpha , then the \Delta neighbours of v are coloured with at most \Delta-1 colours. Thus, by the pigeonhole principle, some pair of neighbours of v use the same colour, so are a good pair for v w.r.t. \alpha . In particular, if G is \Delta -regular, then every unfrozen vertex has a good pair. If G is 3 -connected, then every good pair is in fact a very good pair. A partial (proper) L -colouring assigns colours to some vertices v (from L(v) ), but may leave some vertices uncoloured. To extend a partial L -colouring \gamma_{0} to an L -colouring \gamma means to construct a proper L -colouring \gamma such that \gamma(v)=\gamma_{0}(v) for all vertices v where \gamma_{0}(v) is defined. If |L(v)|\geq\deg(v)+1 for every v\in V(G) , then every partial L -colouring \gamma_{0} can be extended to an L -colouring \gamma . In particular, this is true when L(v)=\{1,\ldots,\Delta+1\} for all v . We call this extending \gamma_{0} to \gamma . Lemma 12 . Let G be a connected graph with a +1 -list-assignment L . Let \alpha,\beta be L -colourings of G . If there exist v\in V(G) and w_{1},w_{2}\in N(v) such that \alpha(w_{1})=\beta(w_{1}) and w_{1},w_{2} are a very good pair for v w.r.t. both \alpha and \beta , then \alpha\sim\beta . Furthermore, there exists a recolouring sequence from \alpha to \beta that recolours neither w_{1} nor w_{2} . Proof. Let G^{\prime}:=G-\{w_{1},w_{2}\} , let L^{\prime}(x):=L(x)\setminus\{\alpha(w_{1})\} for all x\in N(w_{1})\cup N(w_{2}) , and otherwise let L^{\prime}(x):=L(x) . We are done by applying the Key Lemma to G^{\prime} . ∎ Lemma 13 . Let G be a 3 -connected \Delta -regular graph. If \alpha and \beta are unfrozen (\Delta+1) -colourings of G , then \alpha\sim\beta . Proof. Let v be an arbitrary unfrozen vertex in \alpha . By Definition 11 , vertex v has a very good pair w_{1},w_{2} for \alpha . We may assume that w_{1} is unfrozen in \beta . Thus, w_{1} has a very good pair x_{1},x_{2} . Note that \{w_{1},w_{2}\}\cap\{x_{1},x_{2}\}=\varnothing , since x_{1},x_{2}\in N(w_{1}) , but w_{2}\notin N(w_{1}) . First suppose that \alpha(w_{1})\neq\beta(x_{1}) . Form a proper (\Delta+1) -colouring \gamma by colouring w_{1},w_{2} with \alpha(w_{1}) , colouring x_{1},x_{2} with \beta(x_{1}) , and extending. By applying Lemma 12 twice, we get \alpha\sim\gamma\sim\beta . So assume instead, without loss of generality, that \alpha(w_{1})=\beta(x_{1})=1 . For each ordered pair (i,j)\in\{(1,2),(3,2),(3,1)\} , form a proper (\Delta+1) -colouring \gamma_{i,j} by colouring w_{1},w_{2} with i , by colouring x_{1},x_{2} with j , and extending. By applying Lemma 12 four times, we get \alpha\sim\gamma_{1,2}\sim\gamma_{3,2}\sim\gamma_{3,1}\sim\beta ; see Figure 1 . ∎ w_{1} w_{2} x_{1} x_{2} 1 1 \sim \sim \sim \sim \alpha \gamma_{1,2} \gamma_{3,2} \gamma_{3,1} \beta 1 1 2 2 \sim \sim \sim \sim \alpha \gamma_{1,2} \gamma_{3,2} \gamma_{3,1} \beta 3 3 2 2 \sim \sim \sim \sim \alpha \gamma_{1,2} \gamma_{3,2} \gamma_{3,1} \beta 3 3 1 1 \sim \sim \sim \sim \alpha \gamma_{1,2} \gamma_{3,2} \gamma_{3,1} \beta 1 1 \sim \sim \sim \sim \alpha \gamma_{1,2} \gamma_{3,2} \gamma_{3,1} \beta Figure 1 : The harder case in the proof of Lemma 13 , and also of Claim 1 in the proof of Theorem 14 : Vertex names (left) and key colourings (right) in the reconfiguration sequence from \alpha to \beta . In fact, we can weaken the hypothesis in the previous lemma that G is 3 -connected, to require only that G is 2 -connected. Our general idea in the proof below is the same as that in the proof above. However, now it is no longer the case that every good pair is in fact a very good pair. So we must expend more effort ensuring that the pairs we pick are very good. Theorem 14 . Let G be a 2 -connected \Delta -regular graph, with \Delta\geq 3 . If \alpha and \beta are unfrozen (\Delta+1) -colourings of G , then \alpha\sim\beta . Proof. If G is 3 -connected, then we are done by the previous lemma. So instead assume that G has a 2 -cut. Among all 2 -cuts in G , pick a 2 -cut S=\{z_{1},z_{2}\} that leaves a biggest possible component H_{1} . Let H_{2} be another component of G-S . Claim 1 . Fix v_{1},v_{2}\in V(G) such that v_{1} is unfrozen in \alpha and that v_{2} is unfrozen in \beta . If there exists a very good pair x_{1},x_{2} for v_{1} w.r.t. \alpha , there exists a very good pair y_{1},y_{2} for v_{2} w.r.t. \beta , and \{x_{1},x_{2}\}\cap\{y_{1},y_{2}\}=\varnothing , then the theorem holds. Proof. The proof is the same as that of Lemma 13 . First suppose that \alpha(x_{1})\neq\beta(y_{1}) . Form a proper (\Delta+1) -colouring \gamma by colouring x_{1},x_{2} with \alpha(x_{1}) , colouring y_{1},y_{2} with \beta(y_{1}) , and extending. By applying Lemma 12 twice, we have \alpha\sim\gamma\sim\beta . So assume instead, without loss of generality, that \alpha(w_{1})=\beta(x_{1})=1 . For each ordered pair (i,j)\in\{(1,2),(3,2),(3,1)\} , form a proper (\Delta+1) -colouring \gamma_{i,j} by colouring x_{1},x_{2} with i , by colouring y_{1},y_{2} with j , and extending. By applying Lemma 12 four times, we have \alpha\sim\gamma_{1,2}\sim\gamma_{3,2}\sim\gamma_{3,1}\sim\beta ; again, see Figure 1 . ∎ Claim 2 . There exists a vertex v\in V(H_{2}) such that (i) S\not\subseteq N(v) and (ii) if \gamma is a (\Delta+1) -colouring of G and v is unfrozen in \gamma , then v has a good pair w.r.t. \gamma , and every such good pair is a very good pair. In fact, this property holds for every v\in V(H_{2}) such that S\not\subseteq N(v) . Proof. We prove the second statement first. Suppose there exists v\in V(H_{2}) such that S\not\subseteq N(v) ; see the left of Figure 2 . Now consider a (\Delta+1) -colouring \gamma of G in which v is unfrozen. By Definition 11 , there exist w_{1},w_{2}\in N(v) such that \gamma(w_{1})=\gamma(w_{2}) . If G-\{w_{1},w_{2}\} is not connected, then all vertices of H_{1} lie in the same component; furthermore, this component also contains at least one vertex of S , since S\not\subseteq N(v) . But this is a larger component than H_{1} , contradicting our choice of S and H_{1} . Thus, G-\{w_{1},w_{2}\} is connected, as desired. Since \gamma was arbitrary, we have found the desired vertex v ; this proves the second statement. Now we prove the first statement. Assume instead that each v\in V(H_{2}) has S\subseteq N(v) ; see the right of Figure 2 . For each z_{i}\in S , we have \deg_{H_{2}}(z_{i})=|V(H_{2})| . And for each v\in V(H_{2}) , we have \deg_{G}(v)\leq|V(H_{2})|-1+|S|=|V(H_{2})|+1 . Since G is regular, each z_{i}\in S has exactly one neighbour outside H_{2} ; in particular H_{1} and H_{2} are the only components of G-S , since G is 2 -connected and thus each component of G-S must be adjacent to each vertex of S . Furthermore, H_{2} is complete and each vertex of S is complete to H_{2} . If \gamma is a (\Delta+1) -colouring of G with z_{i} unfrozen, then z_{i} has a good pair y_{1},y_{2} w.r.t. \gamma . Since H_{2} is complete, after possibly renaming, we have y_{1}\in V(H_{1}) and y_{2}\in V(H_{2}) . Now G-y_{1} is connected since G is 2 -connected. And G-\{y_{1},y_{2}\} is connected because N(y_{2}) is a clique minus an edge (with endpoints in S ), so any path in G-y_{1} that passes through y_{2} can be rerouted in G-\{y_{1},y_{2}\} through some neighbour of y_{2} in H_{2} . z_{1} z_{2} v z_{1} z_{2} v H_{1} H_{2} S K_{\Delta+1}-z_{1}z_{2} x_{1} y_{1} z_{1} z_{2} x_{2} y_{2} v H_{1} H_{2} Figure 2 : Left: The general case, guaranteed by Claim 2, when there exists v\in V(H_{2}) with S\not\subseteq N(v) . Right: An exceptional case, when no such v exists, and G[V(H_{1})\cup S]=K_{\Delta+1}-z_{1}z_{2} . We assume that z_{1} is unfrozen in \alpha , and that z_{2} is unfrozen in \beta . Let x_{1},x_{2} be a good pair for z_{1} w.r.t. \alpha , and let y_{1},y_{2} be a good pair for z_{2} w.r.t. \beta . By the previous paragraph, each of these good pairs is in fact very good. By possibly swapping indices, we assume that x_{1},y_{1}\in V(H_{1}) and x_{2},y_{2}\in V(H_{2}) . Since z_{1},z_{2} each have only a single neighbour in V(H_{1}) , and G is 2-connected and \Delta -regular for \Delta\geq 3 , we know that x_{1}\neq y_{1} . If x_{2}\neq y_{2} , then the theorem holds by Claim 1 , and we are done; so assume instead that x_{2}=y_{2} . By symmetry, we assume that colours 1 and 2 are both available for z_{2} in \beta , and that \beta(y_{1})=\beta(y_{2})=3 . If y_{2} is unfrozen, then we recolour it, and reuse colour 3 on another neighbour of z_{2} in H_{2} . So assume instead that y_{2} is frozen. Now in \beta recolour z_{2} to unfreeze y_{2} , then proceed as above. Now redefining the good pairs x_{1},x_{2} and y_{1},y_{2} as at the start of the paragraph gives \{x_{1},x_{2}\}\cap\{y_{1},y_{2}\}=\varnothing , so the theorem holds by Claim 1 as explained above. This proves the first statement. ∎ Claim 3 . There exists z\in N(z_{1})\cap N(z_{2})\cap V(H_{2}) and V(H_{2})\subseteq N(z_{1})\cup N(z_{2}) . Proof. By Claim 2 , there exists v\in V(H_{2}) such that S\not\subseteq N(v) ; again, see the left of Figure 2 . We assume that v is unfrozen in \alpha . By Definition 11 , we know v has a good pair w_{1},w_{2} w.r.t. \alpha . By symmetry, we assume that w_{1}\notin S . If S\not\subseteq N(w_{1}) , then we assume that w_{1} is unfrozen in \beta . Similarly, w_{1} has a good pair x_{1},x_{2} w.r.t. \beta . Note that \{w_{1},w_{2}\}\cap\{x_{1},x_{2}\}=\varnothing , so we are done by Claim 1 . Thus, we assume that S\subseteq N(w_{1}) . Let z:=w_{1} . This proves the first statement. Now we prove the second statement. Suppose, to the contrary, that there exists w\in V(H_{2})\setminus(N(z_{1})\cup N(z_{2})) . We assume that w is unfrozen in both \alpha and \beta . Thus, w has a good pair x_{1},x_{2} w.r.t. \alpha , and w has a good pair y_{1},y_{2} w.r.t. \beta . Note that each of these good pairs is very good by Claim 2 . Fix a colour c\notin\{\alpha(x_{1}),\beta(y_{1})\} . Form a proper (\Delta+1) -colouring \gamma_{1} by colouring x_{1},x_{2} with \alpha(x_{1}) , by colouring z_{1},z_{2} with c , and by extending. Similarly, form a proper (\Delta+1) -colouring \gamma_{2} by colouring y_{1},y_{2} with \beta(y_{1}) , by colouring z_{1},z_{2} with c , and by extending. Furthermore, we can choose \gamma_{2} to agree with \gamma_{1} on all components of G-\{z_{1},z_{2}\} other than H_{2} . Now applying Lemma 12 three times, as we explain below, gives \alpha\sim\gamma_{1}\sim\gamma_{2}\sim\beta ; see Figure 3 . x_{1} x_{2} y_{1} y_{2} z_{1} z_{2} 1 1 \sim \sim \sim \alpha \gamma_{1} \gamma_{2} \beta 1 1 3 3 \sim \sim \sim \alpha \gamma_{1} \gamma_{2} \beta 2 2 3 3 \sim \sim \sim \alpha \gamma_{1} \gamma_{2} \beta 2 2 \sim \sim \sim \alpha \gamma_{1} \gamma_{2} \beta Figure 3 : Proving Claim 3: Vertex names (left) and key colourings in the reconfiguration sequence (right). For simplicity, we show the case when \alpha(x_{1})=1,\beta(y_{1})=2,c=3 , and \{x_{1},x_{2}\}\cap\{y_{1},y_{2}\}=\varnothing . However, this intersection could be non-empty and/or we might have \beta(y_{1})=\alpha(x_{1}) . Here \alpha\sim\gamma_{1} and \gamma_{2}\sim\beta follow by applying Lemma 12 to the very good pairs x_{1},x_{2} and y_{1},y_{2} in G , respectively. For \gamma_{1}\sim\gamma_{2} the argument is a bit more subtle since z_{1},z_{2} is not a very good pair in G . Instead we let G^{\prime}:=G[V(H_{2}\cup\{z_{1},z_{2}\}] , and use that z_{1},z_{2} is a very good pair in G^{\prime} with respect to the restrictions \gamma_{1}{{}^{\prime}},\gamma_{2}{{}^{\prime}} of \gamma_{1},\gamma_{2} to G{{}^{\prime}} . By Lemma 12 , we not only have that \gamma_{1}{{}^{\prime}}\sim\gamma_{2}{{}^{\prime}} but also during the implied reconfiguration the colours of the cut-set \{z_{1},z_{2}\} never change. Since \gamma_{1} and \gamma_{2} agree on G-V(G{{}^{\prime}}) , it follows that also \gamma_{1}\sim\gamma_{2} . This proves the second statement. ∎ Consider v\in V(H_{2}) such that S\not\subseteq N(v) ; such a v is guaranteed by Claim 2 . We assume that v is unfrozen in both \alpha and \beta . So by Definition 11 , vertex v has a good pair w.r.t. \alpha and also has a good pair w.r.t. \beta . The argument proving the second statement of Claim 3 actually works unless one of these good pairs intersects S . So assume that the good pair for v w.r.t. \alpha is w_{1},w_{2} with w_{1}\in S ; by symmetry, say w_{1}=z_{1} . This implies that w_{2}\notin N(z_{1}) . So assume that \beta is unfrozen for w_{2} . Now w_{2} has a good pair x_{1},x_{2} w.r.t. \beta . Note that \{w_{1},w_{2}\}\cap\{x_{1},x_{2}\}=\varnothing . Furthermore, both of these good pairs are very good. Thus, we are finished by Claim 1 . ∎ 4 Proof of Connectedness In this section, we prove our Main Theorem: Let G be a connected graph with \Delta\geq 3 and let L be a +1 -list-assignment list-assignment of G . If \alpha,\beta are unfrozen L -colourings, then \alpha\sim\beta . To begin, we sketch the proof. If G is 2 -connected, then we consider whether there exist neighbours v,w such that L(v)\not\subseteq L(w) . If not, then G is regular with identical lists, and so we are done by Theorem 14 . If so, then we recolour \alpha to get an L -colouring \alpha^{\prime} with \alpha^{\prime}(v)\notin L(w) . From \alpha^{\prime} , we use the Key Lemma (applied to G-v ) to reach an L -colouring \beta^{\prime} that agrees with \beta except possibly on N[v] ; and repairing the colouring on N[v] takes a bit of work. This is Lemma 22 . The bulk of our work goes toward the case when G has a cut-vertex. Our proof goes by induction on the number of blocks. We find an endblock H (block with a unique cut-vertex v ), recolour H-v from \alpha to match \beta , and recurse on G-(H-v) . One important subtlety is that our current colouring must remain unfrozen when restricted to this subgraph on which we recurse. When H is neither complete nor a cycle, we can either reuse Lemma 22 , mentioned above, or we can find a very good pair in H , use the Key Lemma to recolour G-H to agree with \beta , and finish on H by the 2 -connected case above. Specifically, if z_{1},z_{2}\in V(H)-v is a very good pair for some vertex w\in V(H)-v , then we apply the Key Lemma to G-\{z_{1},z_{2}\} , which allows us to recolour that subgraph arbitrarily, apart from avoiding on N(z_{1})\cup N(z_{2}) the colour that we are using on z_{1},z_{2} . But since G-H\subseteq G-N(z_{1})\cup N(z_{2}) , we can recolour G-H to match \beta , as desired. When H is either complete or a cycle, we can easily reduce to the case that H=K_{2} . Now walking away from the leaf v in this K_{2} , we continue until we reach a vertex w with \deg(w)\geq 3 . For this v,w -path P , we show how to get the desired colours on P-w , and again recurse on G-(P-w) . To do this, we consider the possibilities that w has two neighbours off of P that are either (i) adjacent or (ii) non-adjacent. These final cases also serve as the base cases of our induction. 4.1 Some Simple Cases In this subsection we handle some simple cases: cycles, paths, complete graphs, the claw, the paw, and 2 -connected graphs with not all lists identical. These preliminary results both help develop intuition, as well as simplify the proof of the Main Theorem. First we explain why in our Main Theorem we require that \Delta\geq 3 . If we did not, the statement would be false, as follows. Example 15 . Let C_{n} be a cycle with vertices v_{1},\ldots,v_{n} , and let e_{i}=v_{i}v_{i+1} (with subscripts modulo n ). For a 3 -colouring \alpha , let f_{\alpha}(e_{i}):=+1 if (\alpha(v_{i}),\alpha(v_{i+1}))\in\{(1,2),(2,3),(3,1)\} and f_{\alpha}(e_{i}):=-1 if (\alpha(v_{i}),\alpha(v_{i+1}))\in\{(2,1),(3,2),(1,3)\} . Finally, let f(\alpha):=\frac{1}{3}\sum_{i=1}^{n}f_{\alpha}(e_{i}) . We call f(\alpha) the winding number of \alpha . It is straightforward to check that f(\alpha) is an integer for all \alpha . It is also easy to verify that if \alpha\sim\beta , then f(\alpha)=f(\beta) . That is, f is invariant under recolouring. To prove this invariance, consider a vertex v_{i} before and after a recolouring step. If v_{i} is recoloured from j to k , then v_{i+1} and v_{i-1} are both coloured \ell , where j,k,\ell\in\{1,2,3\} are distinct. Say \alpha and \alpha^{\prime} are the colourings before and after we recolour v_{i} . So \alpha(e_{i})=-\alpha(e_{i-1}) and \alpha^{\prime}(e_{i})=-\alpha^{\prime}(e_{i-1}) . Thus, f(\alpha^{\prime})=f(\alpha) , as desired. For n\geq 8 , we construct 3 -colourings \alpha and \beta of C_{n} with f(\alpha)\neq f(\beta) . For \alpha , colour v_{1},\ldots,v_{8} as 1,2,1,2,1,2,1,2 ; and for \beta as 1,2,3,1,2,3,1,2 . If n>8 , then we extend both precolourings arbitrarily, but identically. We have \sum_{i=1}^{7}f_{\alpha}(e_{i})=1 , but \sum_{i=1}^{7}f_{\beta}(e_{i})=7 . Thus, f(\alpha)=f(\beta)-2 . In fact, the number of equivalence classes of 3 -colourings of C_{n} is at least \lfloor(n+4)/6\rfloor . To avoid the subtleties in the previous example, we rely on the following sufficient condition. Lemma 16 . Let G=C_{n} , for some n\geq 3 . Fix a 3 -assignment L for G . If \alpha and \beta are L -colourings, neither of which is frozen, and L is not identical on all vertices, then \alpha\sim\beta . Proof. Denote the vertices of G by v_{1},\ldots,v_{n} . Case 1: There exists \bm{i\in\{1,\ldots,n\}} such that \bm{\beta(v_{i})\notin L(v_{i+1})} , with subscripts modulo \bm{n} . First we recolour vertices so that v_{i} uses \beta(v_{i}) ; afterward, we can finish by applying the Key Lemma to G-v_{i} , since |L(v_{i+1})|=3=\deg_{G-v_{i}}(v_{i+1})+2 . So assume that \alpha(v_{i})\neq\beta(v_{i}) , and further that \alpha(v_{i-1})=\beta(v_{i}) ; otherwise, we simply recolour v_{i} with \beta(v_{i}) . Since \alpha is unfrozen, there exists v_{j} that is unfrozen in \alpha ; we assume j=1 (shifting indices if needed). We recolour v_{1} , if needed, to unfreeze v_{2} ; recolour v_{2} , if needed, to unfreeze v_{3} , etc. Eventually, we unfreeze v_{i-1} , recolour it to avoid \beta(v_{i}) , and recolour v_{i} with \beta(v_{i}) . Case 2: We are not in Case 1. Since the lists are not identical, there exists a vertex v_{i} with L(v_{i})\not\subseteq L(v_{i+1}) . So there exists an L -colouring \gamma with \gamma(v_{i})\notin L(v_{i+1}) . By applying Case 1 (twice), we have \alpha\sim\gamma\sim\beta . ∎ Paths exhibit the same subtlety as cycles. To see this intuitively, we view a path and its lists as being formed from a cycle and its (identical) lists, by fixing the colours on one or more successive cycle vertices and deleting them, as well as deleting colours on deleted vertices from the lists of their undeleted neighbours. Starting from inequivalent 3 -colourings of cycles, we get the same for paths. This motivates our interest in the following sufficient condition for equivalence. Lemma 17 . Let G=P_{n} , for some n\geq 3 . Fix a +1 -list-assignment L for G . If \alpha and \beta are both unfrozen L -colourings and |\cup_{v\in V(G)}L(v)|\geq 4 , then \alpha\sim\beta . Proof. Denote V(G) by v_{1},\ldots,v_{n} . We assume that |L(v_{i})|\leq 3 for all i , or we are done by the Key Lemma. So by the hypothesis |\cup_{v\in V(G)}L(v)|\geq 4 , there exists i such that L(v_{i})\not\subseteq L(v_{i+1}) and L(v_{i+1})\not\subseteq L(v_{i+1}) . We assume that \alpha(v_{i})\notin L(v_{i+1}) and \alpha(v_{i+1})\notin L(v_{i}) . If this is not the case, then we construct such an L -colouring \gamma . By the case we consider below, \alpha\sim\gamma\sim\beta , as desired. We start from \alpha and recolour, as follows, to reach \beta . By Observation 10 , we assume that v_{i} is unfrozen in \beta . As long as v_{i} is coloured from \alpha(v_{i}) , vertex v_{i+1} remains unfrozen, so we can use v_{i+1} to put \beta(v_{j}) on v_{j} for all j\geq i+3 . (The proof is by induction on n-j .) After we have v_{j} coloured with \beta(v_{j}) for all j\geq i+3 , we recolour v_{i+1} with \alpha(v_{i+1}) . By swapping the roles of i+1 and i , we can use vertex v_{i} to recolour v_{j} with \beta(v_{j}) for all j\leq i-2 . (Equivalently, we relabel each vertex v_{j} as v_{n+1-j} and repeat the steps above.) So the only vertices where our current colouring differs from \beta are contained in \{v_{i-1},v_{i},v_{i+1},v_{i+2}\} . By relabeling, we call these vertices v_{1},v_{2},v_{3},v_{4} , and call the current colouring \alpha . Recall that v_{2} is unfrozen in \beta . If \beta(v_{1})\neq\alpha(v_{2}) , then in \beta recolour v_{2} with \alpha(v_{2}) ; now we can recolour v_{1} with \alpha(v_{1}) and can recolour v_{3},v_{4} to match \alpha , since v_{3} is unfrozen. Otherwise, we recolour v_{1} to avoid \alpha(v_{1}) , first recolouring v_{2} to unfreeze v_{1} if needed, and conclude as above. ∎ The following lemma is easy to verify, essentially by brute force. But stating it explicitly is convenient for simplifying later proofs. Lemma 18 . Let G=P_{3} and L be a +1 -list-assignment for G . If \alpha,\beta are unfrozen L -colourings, then \alpha\sim\beta . Proof. Denote V(G) by v_{1},v_{2},v_{3} . If L(v_{1})\not\subseteq L(v_{2}) , then we colour v_{1} from L(v_{1})\setminus L(v_{2}) , colour v_{2} and v_{3} as desired, then recolour v_{1} if needed. So assume L(v_{1})\subseteq L(v_{2}) ; similarly, assume L(v_{3})\subseteq L(v_{2}) . By symmetry, assume L(v_{1})=\{1,2\} , L(v_{2})=\{1,2,3\} , and L(v_{3})=\{1,a\} with a\in\{2,3\} . For each value of a , there exist at most 5 unfrozen L -colourings, and we check easily. ∎ Lemma 19 . Let G be formed from the claw K_{1,3} by subdividing a single edge 0 or more times. If L is a +1 -list-assignment for G and \alpha,\beta are unfrozen L -colourings, then \alpha\sim\beta . Proof. Let v be the 3 -vertex, with neighbours w_{1},w_{2},w_{3} , with w_{1} and w_{2} being 1 -vertices, and with w_{3} being either a 1 -vertex or 2 -vertex. Let P denote the path starting at v and continuing through w_{3} until we reach a leaf. We assume that v is unfrozen in both \alpha and \beta . We first show that we can assume that V(P)=\{v,w_{3}\} , by showing that \alpha\sim\gamma for some colouring \gamma that agrees with \beta on G-\{v,w_{1},w_{2},w_{3}\} and has v unfrozen. Fix c\in L(v)\setminus L(w_{3}) . If c is used on both w_{1} and w_{2} , then choose a partial colouring \gamma that agrees with \beta on G-\{v,w_{1},w_{2},w_{3}\} and agrees with \alpha on \{w_{1},w_{2}\} , and extend it greedily to G . Applying the Key Lemma to G-\{w_{1},w_{2}\} (in which the size of the reduced list of v is at least two larger than its degree) yields \alpha\sim\gamma , as desired. So instead assume c is used on at most one of w_{1} and w_{2} ; say w_{1} . Since v is unfrozen, we can recolour it if needed to unfreeze w_{1} , then recolour w_{1} , and recolour v with c . So we assume v is unfrozen under \alpha , and uses colour c . Next choose a partial colouring \gamma that agrees with \beta on G-\{v,w_{1},w_{2},w_{3}\} and agrees with \alpha on \{v,w_{1},w_{2}\} and extend it to w_{3} . Now apply the Key Lemma to G-\{v,w_{1},w_{2}\} (in which the size of the reduced list of w_{3} is at least two larger than its degree) to obtain \alpha\sim\gamma . In both cases we managed to recolour \alpha to match \beta on P-\{v,w_{3}\} . Thus, we assume w_{3} is a 1 -vertex. That is G=K_{1,3} . Now suppose L(w_{1})\nsubseteq L(v) . We recolour w_{1} from L(w_{1})\setminus L(v) , and can recolour G-w_{1} by Lemma 18 , afterward recolouring w_{1} to \beta(w_{1}) if needed. So we assume L(w_{i})\subseteq L(v) for all i\in\{1,2,3\} . We also assume v is unfrozen in \alpha . Thus, we have \alpha(w_{i})=\alpha(w_{j}) for distinct i,j\in\{1,2,3\} . So we can recolour v,w_{k} , where k=\{1,2,3\}\setminus\{i,j\} so that w_{k} uses \beta(w_{k}) . Afterward, w_{i} and w_{j} still have the same colour so v remains unfrozen under \alpha , and we can finish on G-w_{k} by Lemma 18 . ∎ Lemma 20 . Let G be formed from the paw K_{1,3}+e by subdividing the pendent edge 0 or more times. If L is a +1 -list-assignment for G and \alpha,\beta are unfrozen L -colourings, then \alpha\sim\beta . Proof. We label the vertices similarly to the proof of the previous lemma; the arguments are also similar, but we will no longer explicitly describe the intermediate colourings \gamma . Let v be the 3 -vertex, let w_{1} and w_{2} be adjacent 2 -vertices, and let w_{3} be either a 1 -vertex or an interior vertex of a path starting at v and ending at leaf; we call this path P . We assume that v is unfrozen in both \alpha and \beta . We first show that we can assume V(P)=\{v,w_{3}\} ; assume not. If L(w_{1})\not\subseteq L(v) , then we recolour w_{1} from L(w_{1})\setminus L(v) , and apply the Key Lemma to G-w_{1} to obtain a colouring that agrees with \beta on P-\{v,w_{3}\} , with v unfrozen. Thus, we assume that L(w_{i})\subseteq L(v) for each i\in\{1,2\} . Further, we assume that L(w_{1})\subseteq L(w_{2}) , as otherwise we can recolour w_{1} from L(w_{1})\setminus L(w_{2}) and apply the Key Lemma to G-w_{1} as before, and then recolour w_{2} if necessary to unfreeze v again. So by symmetry, we assume L(v)=\{1,2,3,4\} and L(w_{1})=L(w_{2})=\{1,2,3\} . Since v is unfrozen in \alpha , either \alpha(w_{3})\notin L(v) or else \alpha(w_{3})=\alpha(w_{i}) for some i\in\{1,2\} . In either case, it is easy to recolour v (and possibly w_{j} with j=3-i ) so that v is coloured from L(v)\setminus L(w_{3}) . Now by applying the Key Lemma to P-\{v\} , we can recolour it to agree with \beta on P-\{v,w_{3}\} . If v is frozen after this, we recolour w_{3} to unfreeze it. Thus, we assume that V(P)=\{v,w_{3}\} as claimed. That is, G=K_{1,3}+e . Recolour v , if needed, to unfreeze w_{3} . For simplicity, call the present colouring \alpha (even after the previous paragraph). By symmetry between w_{1} and w_{2} , assume \alpha(v)\neq\beta(w_{2}) . Form \alpha^{\prime} from \alpha by recolouring w_{2} with \beta(w_{2}) and recolouring w_{1} arbitrarily. By Lemma 21 (the proof of which does not need the present lemma), we can recolour \alpha to \alpha^{\prime} . Now restricting to G-w_{2} , we can recolour \alpha^{\prime} to \beta by Lemma 18 , since w_{3} is unfrozen in \alpha^{\prime} and v is unfrozen in \beta . ∎ The next lemma (actually, just its non-trivial direction) is a special case of the lemma that follows it. However, in this case we can give a proof that is independent of the Key Lemma. This simpler proof leads to a sharper bound on the diameter, which is in fact nearly optimal. Lemma 21 . Let G=K_{n} , with n\geq 2 , and fix a +1 -list-assignment L . If |\cup_{v\in V(G)}L(v)|=n , then all lists are identical and every L -colouring of G is frozen. Otherwise, \alpha\sim\beta for all L -colourings \alpha,\beta . In fact, in the latter case, \textrm{dist}_{\mathcal{C}(G,L)}(\alpha,\beta)\leq 3n/2+2 . Proof. The ‘if’ statement is trivial, since every colour in \cup_{v\in V(G)}L(v) is used in every L -colouring. Now we prove the ‘otherwise’ statement. Fix L -colourings \alpha,\beta . We build a digraph \vec{D} , with V(\vec{D})=V(G) and \vec{vw}\in E(\vec{D}) if \beta(v)=\alpha(w) . Note that \Delta^{+}(\vec{D})\leq 1 and \Delta^{-}(\vec{D})\leq 1 . So \vec{D} consists of directed paths, directed cycles, and isolated vertices. A bad cycle is a directed cycle in \vec{D} for which all colours in the lists of its vertices are used either on other cycles or isolated vertices (which already have the correct colour). If a cycle is not bad, then it is good . We prove the stronger bound \textrm{dist}_{\mathcal{C}(G,L)}(\alpha,\beta)\leq|E(\vec{D})|+\#\text{cycles}(\vec{D})+2\times\mathbf{1} , where \mathbf{1} is the indicator function for \vec{D} containing a bad cycle. Our proof is by induction on |E(\vec{D})| ; the base case |E(\vec{D})|=0 holds trivially. Suppose \vec{D} contains a good cycle. Specifically, there exists a directed cycle \vec{C} and a colour c and a vertex v\in\vec{C} such that c\in L(v) , but c is not currently used on any vertex of G . Recolour v with c , which opens \vec{C} into a directed path, \vec{P} . Let x be a sink of \vec{P} . Recolouring x with \beta(x) removes one arc from \vec{P} ; we repeat this process until all vertices of \vec{P} are coloured correctly. More broadly, in the same way we handle every good cycle. So if \vec{D} contains a cycle, then we assume it is a bad cycle, and \mathbf{1}=1 . We handle all bad cycles together at the end. Suppose \vec{D} contains a directed path. Similar to above, we recolour the sink x of the path with \beta(x) , which shrinks the path by an edge, and we handle the shorter path similarly. So we assume \vec{D} contains no paths. Note that recolouring good cycles and paths never creates bad cycles. Finally, suppose \vec{D} contains only bad cycles (and isolated vertices). Since |\cup_{x\in V(G)}L(x)|>n , there exists an isolated vertex w with c\in L(w) that is currently unused on V(G) . By recolouring w with c we ‘unlock’ every bad cycle of \vec{D} (changing it to a good cycle), recolour to fix all of these bad cycles, and then recolour w with \beta(w) . The key observation is that, because we unlock every bad cycle at once, we only need to perform this unlocking step at most once. So the total number of recolouring steps is at most |E(\vec{D})|+\#\text{cycles}(\vec{D})+2\times\mathbf{1} . Since each cycle has length at least 2 , this gives the claimed bound 3n/2+2 . (With a bit more care, we can improve this bound to (3n+1)/2 , which is sharp.) ∎ Now we handle the general case of 2 -connected graphs with lists that are not all identical. Lemma 22 . Let G be a connected graph with a +1 -list-assignment L . If there exist v,w\in V(G) such that vw\in E(G) , L(v)\not\subseteq L(w) , and G-v is connected, then \alpha\sim\beta whenever \alpha and \beta are both unfrozen L -colourings. Proof. It suffices to consider the case when \alpha(v)\notin L(w) . If not, then we form a new L -colouring \gamma by first colouring v from L(v)\setminus L(w) and then colouring each other vertex arbitrarily from its list to get a proper L -colouring. (This is possible since L is a +1 -list-assignment.) By the case we consider below, we have \alpha\sim\gamma\sim\beta , as desired. By Observation 10 , we assume that v is unfrozen in \beta . If |\beta^{-1}(\alpha(v))\cap N(v)|\neq 1 , then let \beta_{0}:=\beta . Otherwise, let x be the unique vertex in \beta^{-1}(\alpha(v))\cap N(v) . We assume x is unfrozen, by recolouring v if needed; let \beta_{0} be the resulting colouring. Form \beta_{1} from \beta_{0} by recolouring v with \alpha(v) and recolouring each z\in N(v)\cap\beta_{0}^{-1}(\alpha(v)) from L(z)\setminus\left(\{\alpha(v)\}\cup\bigcup_{y\in N(z)\setminus\{v\}}\beta_{0}(y)\right) . (Again, this is possible because L is a +1 -list-assignment.) To move from \alpha to \beta_{1} , we let G^{\prime}:=G-v , let L^{\prime}(z):=L(z)\setminus\{\alpha(v)\} when z\in N(v) , and let L^{\prime}(z):=L(z) otherwise. By hypothesis, G^{\prime} is connected. Since L^{\prime} is a +1 -list-assignment for G^{\prime} , and |L^{\prime}(w)|\geq\deg_{G^{\prime}}(w)+2 , the Key Lemma gives \alpha|_{G^{\prime}}\sim_{L^{\prime}}\beta_{1}|_{G^{\prime}} ; thus \alpha\sim_{L}\beta_{1} . We now consider three cases based on |\beta^{-1}_{0}(\alpha(v))\cap N(v)| : it is at least 2 , it is 0 , or it is 1 . If |\beta^{-1}_{0}(\alpha(v))\cap N(v)|=0 , then \beta_{0} differs from \beta_{1} only on v . Recolouring v in \beta_{1} with \beta_{0}(v) shows that \beta_{1}\sim\beta_{0} ; hence \alpha\sim\beta_{1}\sim\beta_{0}\sim\beta , as desired. Suppose instead that |\beta^{-1}_{0}(\alpha(v))\cap N(v)|\geq 2 . Note that in \beta_{1} vertex w is unfrozen because \beta_{1}(v)=\alpha(v)\notin L(w) . So starting from \beta_{1} we recolour w , if needed, to unfreeze v and recolour v . This makes colour \alpha(v) available for all z in the independent set \beta^{-1}_{0}(\alpha(v))\cap N(v) . After recolouring all such z with \alpha(v) , we recolour v , if needed, to avoid \beta_{0}(w) ; this is possible because |\beta^{-1}_{0}(\alpha(v))\cap N(v)|\geq 2 . Finally, we recolour w with \beta_{0}(w) and recolour v with \beta_{0}(v) . Thus, we have \alpha\sim\beta_{1}\sim\beta_{0}\sim\beta whenever |\beta^{-1}_{0}(\alpha(v))\cap N(v)|\neq 1 . Finally, assume instead that |\beta^{-1}_{0}(\alpha(v))\cap N(v)|=1 . As above, we again let x be the unique vertex in \beta^{-1}_{0}(\alpha(v))\cap N(v) . Note that \beta_{1}(z)=\beta_{0}(z) for all z\notin\{v,x\} . Let G^{\prime}:=G[\{v,w,x\}] and L^{\prime}(z):=L(z)\setminus\cup_{y\in N(z)\setminus\{v,w,x\}}\beta_{1}(y) for all z\in\{v,w,x\} . Let \beta_{i}^{\prime} denote the restriction to G^{\prime} of \beta_{i} for each i\in\{1,2\} . So it suffices to show that \beta_{0}^{\prime}\sim_{L^{\prime}}\beta_{1}^{\prime} . Note that v is unfrozen in \beta_{0}^{\prime} and w is unfrozen in \beta_{1}^{\prime} . If G^{\prime}\cong K_{3} , then |L^{\prime}(z)|\geq 3 for all z\in\{v,w,x\} , but |\cup_{z\in\{v,w,x\}}L^{\prime}(z)|\geq 4 since \alpha(v)\in L^{\prime}(v)\setminus L^{\prime}(w) , so by Lemma 21 we get \beta_{1}^{\prime}\sim_{L^{\prime}}\beta_{0}^{\prime} . Thus, we assume that wx\notin E(G) , so G^{\prime}\cong P_{3} . Hence |L^{\prime}(v)|\geq 3 , |L^{\prime}(w)|\geq 2 , |L^{\prime}(x)|\geq 2 . So we are done by Lemma 18 . ∎ 4.2 Proof of the Main Theorem In this section, we prove our Main Theorem. For convenience, we restate it below. Theorem 23 . Let G be a connected graph with \Delta\geq 3 , and let L be a +1 -list-assignment. If \alpha and \beta are both unfrozen L -colourings, then \alpha\sim\beta . In fact, \textrm{dist}_{\mathcal{C}(G,L)}(\alpha,\beta)=O(|V(G)|^{2}) . Proof. Our proof is by induction on the number of blocks in G , and it follows the outline we gave just before Section 4.1 . The base case is when (i) G is formed from K_{1,3} by subdividing a single edge 0 or more times, (ii) G is formed from K_{1,3}+e by subdividing the pendent edge 0 or more times, or (iii) G is 2 -connected with |V(G)|\geq 3 . Cases (i) and (ii) are handled by Lemmas 19 and 20 . Case (iii) is handled by either Theorem 14 or Lemma 22 . Now suppose that G has a cut-vertex. Let H be a leaf in the block tree, with a unique cut-vertex v . Let w be a neighbour of v in H . Claim 1 . L(w)\subseteq L(v) and L(x)=L(w) for all x\in V(H)-v . Proof. Suppose there exist distinct vertices x_{1},x_{2}\in V(H)-v with L(x_{1})\neq L(x_{2}) . Since H-v is connected, we can assume that x_{1}x_{2}\in E(H) . By symmetry, we assume that L(x_{1})\not\subseteq L(x_{2}) . But now we are done by Lemma 22 . Thus, we assume that L(x_{1})=L(x_{2}) ; hence, L(x)=L(w) for all x\in V(H)-v . Furthermore, if L(w)\not\subseteq L(v) , then we are again done by Lemma 22 . This proves the claim. ∎ Claim 2 . If H is not a cycle, clique, or clique with an edge subdivided (to create vertex v ), then there exist x,y\in V(H)-v such that \textrm{dist}(x,y)=2 and H-\{x,y\} is connected. Proof. By Claim 1 , and the fact that H is not a cycle, all vertices in H-v have equal degrees, which are at least 3 . First suppose that there exists z\in V(H) such that \textrm{dist}(v,z)\geq 3 . Note that z has non-adjacent neighbours, say x,y (since H-v is connected and all its vertices have the same degree in G ). If H-\{x,y\} is connected, then we are done. Assume instead that H-\{x,y\} is not connected; so y is a cut-vertex in H-x . Thus, H-x has at least two endblocks, and each has a non-cut-vertex adjacent to x ; call these x^{\prime} and y^{\prime} . Now H-\{x^{\prime},y^{\prime}\} is connected (since \deg(x)\geq 3 ), and \textrm{dist}(x^{\prime},y^{\prime})=2 , as desired. Assume instead that \textrm{dist}(v,z)\leq 2 for all z\in V(H)-v . Let V_{i}:=\{z\in V(H):\textrm{dist}(v,z)=i\} for each i\in\{1,2\} . And let H_{i}:=H[V_{i}] . We assume that V_{2}\neq\varnothing (otherwise, we simply let x,y be non-adjacent vertices in H_{1} , which exist because H is not a clique). If any vertex of V_{1} has neighbours in at least two components of H_{2} , then we are done; so assume not. Note that each component of H_{2} has at least two neighbours in H_{1} , since H is 2 -connected. Note that each component of H_{2} must be a clique, or we pick x,y in such a component, and we are done. Similarly, if x\in H_{1} has a neighbour in some component C of H_{2} , then x is adjacent to all vertices of C (or we take y to be a nearest non-neighbour in H_{2} ). If any vertex x in V_{1} has no neighbour in V_{2} , then we are done (note that some such x is distance 2 from some vertex y\in V_{2} , and H-\{x,y\} is connected); so assume not. If H_{2} has at least two components, then there exist x,x^{\prime}\in V_{1} adjacent to different components of H_{2} such that xx^{\prime}\in E(H) (since H-v is connected). So if H_{2} has at least two components then we are done; consider x,x^{\prime}\in V_{1} with neighbours in different components, and pick y\in V_{2} adjacent to x^{\prime} . Now \textrm{dist}(x,y)=2 and H-\{x,y\} is connected. Thus, we conclude that H_{2} has a single component. If H_{1} has at least three vertices, then let x,y be any non-adjacent pair (such a pair exists, since all vertices in V_{1}\cup V_{2} have the same degree, but each vertex of V_{1} is adjacent to v ). So we conclude that |V_{1}|=2 . But now H is formed from a clique by subdividing a single edge (with the vertices in V_{1} as its endpoints) to form v ; this contradicts the hypothesis. ∎ Claim 3 . H is an edge, cycle, or a larger clique. Proof. First suppose that H is not a clique with an edge subdivided (to create vertex v ). By the previous claim, there exist x,y\in V(H)-v such that \textrm{dist}(x,y)=2 and H-\{x,y\} is connected. Let z be a common neighbour of x and y . We assume that v is unfrozen in both \alpha and \beta . By Claim 2 , L(x)=L(y) so there exists a colouring \gamma_{1} that uses a common colour c on x and y and agrees with \alpha on G-V(H) . Similarly, there exists a colouring \gamma_{2} that also uses c on x and y and agrees with \beta on G-V(H) . Let \alpha^{\prime},\beta^{\prime},\gamma_{1}^{\prime},\gamma_{2}^{\prime} denote the restrictions to H of \alpha,\beta,\gamma_{1},\gamma_{2} . Form L^{\prime} from L by restricting to H and deleting from L(v) all colours used by \alpha on neighbours of v in G-H . Since \alpha^{\prime} and \gamma_{1}^{\prime} are both unfrozen, by the base case, \alpha^{\prime}\sim_{L^{\prime}}\gamma_{1}^{\prime} ; thus, \alpha\sim_{L}\gamma_{1} . Analogously \beta\sim_{L}\gamma_{2} . Furthermore, \gamma_{1}\sim_{L}\gamma_{2} , by Lemma 12 applied to the very good pair x,y . Hence, \alpha\sim\gamma_{1}\sim\gamma_{2}\sim\beta , as desired. Finally, assume that H is formed from a clique by subdividing a single edge (to create v ). Let x,y denote the neighbours in H of v . Since L(x)=L(y) and N(x)=N(y) , by possibly recolouring y we can assume that \alpha(x)=\alpha(y) and \beta(x)=\beta(y) . So we can form G^{\prime} from G by identifying x and y . But now |L(v)|\geq\deg_{G^{\prime}}(v)+2 , so we are done by the Key Lemma. ∎ Claim 4 . H is an edge. Proof. Suppose H is a larger clique (order at least 3 ). Recall that v is the unique cut-vertex of H , and let u be a neighbour of v not in H . Make u unfrozen in both \alpha and \beta . Form \alpha^{\prime} from \alpha by recolouring H as in \beta , except that v keeps it colour and if some neighbour x of v in H has \beta(x)=\alpha(v) , then x is coloured arbitrarily (if no such x exists, then choose x to be an arbitrary neighbour in H of v ). Finally, if needed, recolour u so that |\cup_{y\in H}L_{H}(y)|>|H| ; to form L_{H}(v) from L(v) , delete all colours used on neighbours of v outside H . Now we can recolour H from \alpha to \alpha^{\prime} . Note that u is unfrozen in \beta (by assumption) and in \alpha^{\prime} since the open neighbourhood N(u) is coloured identically in \alpha^{\prime} and \alpha . Let G^{\prime}:=G-(H-\{v,x\}) . Since \alpha^{\prime} agrees with \beta in H-\{v,x\} , we can restrict to G^{\prime} whenever \Delta(G^{\prime})\geq 3 . But if \Delta(G^{\prime})\leq 2 , then we form G^{\prime\prime} from G^{\prime} by adding back another neighbour of v (in H ), and G^{\prime\prime} is handled by Lemma 20 . Assume instead that H is a 4^{+} -cycle. Let v be a cut-vertex of H and u be a neighbour of v not in H . We assume that u is unfrozen in \alpha and recolour u , if needed, to ensure that |\cup_{x\in H}L_{H}(x)|\geq 4 ; here for L_{H}(v) we remove from L(v) all colours used on N(v)\setminus V(H) , and otherwise, L_{H}(x):=L(x) . Form \alpha^{\prime} from \alpha by recolouring H-v as in \beta , and colouring v arbitrarily to make the colouring proper. (Possibly we need \alpha^{\prime}(v)\neq\beta(v) because \alpha^{\prime}(y)=\alpha(y)=\beta(v) for some y\in N(v)\setminus V(H) .) We also know that \alpha^{\prime} is unfrozen on H because |\cup_{x\in H}L_{H}(x)|\geq 4 , by construction. Thus, we can assume \alpha^{\prime} is unfrozen on N[v]\cap V(H) ; if not, then we ‘push’ this unfrozenness around the cycle (we do this in both \alpha^{\prime} and \beta , since all vertices in V(H)\setminus N[v] have identical colourings of their closed neighbourhoods in \alpha^{\prime} and \beta ). Let z be an arbitrary neighbour of v in N[v]\cap V(H) ; further, pick z to be unfrozen (in \alpha^{\prime} ) if v is frozen. So we can restrict to G-(H-\{v,z\}) ; this works since in \beta vertex u is unfrozen, and in \alpha^{\prime} either v or z is unfrozen. ∎ By the previous claim, every endblock is K_{2} . Let P be a maximal path, containing some endblock, such that all internal vertices of P have degree 2 in G . Let v be an endpoint of P such that \deg_{G}(v)\geq 3 . Pick neighbours w,x of v , not in P , as follows. If possible, pick w,x to be non-adjacent; otherwise, if possible, pick w to be a cut-vertex. Let y be the neighbour of v on P . First suppose that w,x are non-adjacent. Consider the subgraph J induced by \{w,x\}\cup V(P) ; note that J is formed from K_{1,3} by subdividing one edge 0 or more times. To begin, we show that we can assume that V(P)=\{v,y\} . By Observation 10 , we assume that w is unfrozen in \alpha . Form \alpha^{\prime} from \alpha by recolouring V(P)-\{v,y\} to agree with \beta and recolouring y arbitrarily to give a proper colouring; note that w is also unfrozen in \alpha^{\prime} . Now we can recolour \alpha to \alpha^{\prime} by Lemma 19 , and recurse on G-(P-\{v,y\}) ; that is, we can assume that V(P)=\{v,y\} , as desired. Our goal now is to recurse on G-y . To this end, we form \alpha^{\prime\prime} from \alpha^{\prime} by recolouring y with \beta(y) , recolouring v with a colour not in L(y) , and recolouring w and x arbitrarily to get a proper colouring. Note that y is unfrozen under \alpha^{\prime\prime} , due to the colour of v . Again by Lemma 19 , we can recolour from \alpha^{\prime} to \alpha^{\prime\prime} . If G-y is a path, then G is a subdivision of K_{1,3} . In that case we can apply the above reduction via Lemma 19 to each of the maximal paths incident to the central vertex, after which we have reduced to the case that the graph is K_{1,3} and we can finish by applying Lemma 19 one final time. Thus, we assume that G-y is neither a path nor a cycle (since every end-block is an edge). As \alpha^{\prime\prime}(y)=\beta(y) , we can recurse on G-y if it contains an unfrozen vertex; so assume it does not. In particular, we assume that v,w,x are frozen and that y is the only unfrozen vertex. In this case we will recolour G[\{v,w,x,y\}] to unfreeze one of v,w,x . By symmetry, we assume that L(v)=\{1,2,3,4\} , \alpha^{\prime\prime}(v)=1 , L(y)=\{2,3\} , \alpha^{\prime\prime}(y)=\beta(y)=2 , L(w)=\{1,3\} , \alpha^{\prime\prime}(w)=3 , L(x)=\{1,4\} , and \alpha^{\prime\prime}(x)=4 . Now we recolour y with 3, v with 2, w and x with 1, v with 4, and y with 2. Now v is unfrozen, and we used the final two recolourings to ensure that y ends up with colour \beta(y) again. So now we can recurse on G-y . Suppose instead that w,x are adjacent. First suppose that w is a cut-vertex. As in the previous paragraph, we let J:=G[\{w,x\}\cup V(P)] , and we can assume that V(P)=\{v,y\} by Lemma 20 . We recolour J[\{v,w,x,y\}] so that y matches \beta(y) . If at least one of v,w,x is unfrozen, then we’re done by induction on G-y ; so assume instead that only y is unfrozen. Up to renaming colours, we assume that L(v)=\{1,2,3,4\} , \alpha^{\prime\prime}(v)=1 , L(y)=\{2,3\} , \alpha^{\prime\prime}(y)=2 , L(w)=\{1,3,4\} , \alpha^{\prime\prime}(w)=3 , L(x)=\{1,3,4\} , and \alpha^{\prime\prime}(x)=4 . Now we recolour y with 3, v with 2, w with 1, and x with 3. Now we can get any colours we like (in particular \beta ) on all vertices that are not neighbours of x and lie in the component H^{\prime} of G-\{x,y\} that contains v . This uses Lemma 12 on the very good pair x,y in G[V(H^{\prime})\cup\{x,y\}] . Since w is a cut-vertex, this fixes the colouring on at least one additional block. Similarly, if H^{\prime} is the block of G containing v,w,x , then this approach works if any vertex of H^{\prime} is a cut-vertex in G-\{x,y\} . Thus, we conclude that H^{\prime} is an endblock; in fact, G consists only of H^{\prime} and P . But now H^{\prime} must be K_{2} , by Claim 4 above, which is a contradiction. This finishes the inductive step and completes the proof. ∎ Remark . We note that the implicit multiplicative constant, call it C , in the bound \diam\mathcal{C}(G,L)=O(|V(G)|^{2}) need not be too large. We have not made an effort to optimise C , but it is straightforward to check that we can take C=10 . 4.3 Few Frozen Colourings To complete the proof of the Main Theorem, it remains to show that the number of frozen colourings is vanishingly small compared to the total number of proper colourings, provided \Delta is sufficiently small compared to n . Lemma 24 . Consider a +1 -list-assignment L for a connected graph G with n vertices and maximum degree \Delta . Let \mathcal{C}(G,L)^{f} denote the collection of frozen L -colourings of G . Then \frac{|\mathcal{C}(G,L)^{f}|}{|\mathcal{C}(G,L)|}\leq 2^{-n/\Delta^{4}}, unless G is a complete graph. Proof. Consider a set S=\{v_{1}w_{1},v_{2}w_{2},\ldots,v_{s}w_{s}\} of edges such that (N[v_{i}]\cup N[w_{i}])_{i\in\{1,\ldots,s\}} are disjoint sets of vertices, and N[v_{i}]\neq N[w_{i}] for all i . Given a colouring c and edge vw , the swap of c at vw is the colouring c^{\prime} given by c^{\prime}(v)=c(w),c^{\prime}(w)=c(v) and c^{\prime}(x)=c(x) for all x\notin\{v,w\} . For a subset M\subseteq S , the swap of c at M is obtained by swapping at each edge of M . We claim that if c is frozen and M\neq\varnothing , then the swap at M is proper and unfrozen. If M consists of one edge vw this follows because c(N[v])=L(v) and c(N[w])=L(w) in a frozen colouring, ensuring the swap of c at vw remains proper. Since N[v]\neq N[w] , without loss of generality there is a vertex x_{vw}\in N[v]\setminus N[w] , so in the swap of c at vw the colour c(v) is in L(x_{vw})\setminus N[x_{vw}] , showing that the swap is unfrozen. The fact that the sets (N[v_{i}]\cup N[w_{i}])_{i\in\{1,\ldots,s\}} are disjoint ensures that the vertices x_{v_{i}w_{i}} are disjoint and that each of them is adjacent to at most one edge in S , so that swapping additional edges of S preserves their unfrozenness. Let g_{M}:\mathcal{C}(G,L)^{f}\rightarrow\mathcal{C}(G,L) be the function that maps a frozen colouring c to the colouring swapped at M . By the above \{g_{M}(\mathcal{C}(G,L)^{f}):\varnothing\neq M\subseteq S\} are disjoint sets of unfrozen colourings, each of size |\mathcal{C}(G,L)^{f}| . There are 2^{|S|}-1 non-empty choices for M , so \frac{|\mathcal{C}(G,L)^{f}|}{|\mathcal{C}(G,L)|}\leq 2^{-|S|}. It remains to show that S can be chosen of size at least n/\Delta^{4} . For this consider a maximum independent set I of G^{4} . This ensures that for any two vertices v_{i},v_{j}\in I , the distance between v_{i} and v_{j} is at least 5 . Note that for every v_{i}\in I , there is an edge v_{i}w_{i} of G such that N[v_{i}]\neq N[w_{i}] (indeed: if not, then G is the complete graph on N[v_{i}] ). For every v_{i}\in I select one arbitrary such edge v_{i}w_{i} , and include it in S . Since the distance between v_{i} and v_{j} is at least 5 , we have that N[v_{i}]\cup N[w_{i}] and N[v_{j}]\cup N[w_{j}] are disjoint, for all distinct v_{i},v_{j}\in I . Since the maximum degree of G^{4} is less than \Delta^{4} , it follows that |S|=|I|\geq n/\Delta^{4} , as desired. ∎ 5 Sharpness and Open Questions It is natural to ask if our Main Results can be strengthened or extended. To show that we cannot strengthen the Main Theorem by lowering even just one list-size, we first describe examples that imply the Shattering Observation. After that, we discuss some possible extensions of our Main Results, particularly those for correspondence colouring. Lemma 25 . There exist connected graphs G with list-assignments L in which |L(w)|=\deg(w) for one vertex w and |L(v)|\geq\deg(v)+1 for all other vertices, such that the L -recolouring graph has exponentially many non-singleton components. Proof. Let K_{n} be the complete graph in which all vertices are assigned the same list L(v)=\{1,\ldots,n\} . Then we have |L(v)|\geq\deg(v)+1 for all vertices and \mathcal{C}(K_{n},L) has just n! singleton components. Add a new vertex x , connect it to one vertex w of K_{n} , and set L(x)=\{n+1,\ldots,n+p\} for some p\geq 2 . The resulting graph and list-assignment satisfies the conditions in the claim, and the L -recolouring graph is formed of n! components of size p . ∎ While the simple example given in Lemma 25 is very irregular, it is not too difficult to construct \Delta -regular examples as well, for any odd \Delta\geq 5 . The examples we found use many distinct lists, though. As a counterpoint to Theorem 1 , it could be interesting to try to strengthen Lemma 25 by restricting to \Delta -regular graphs with essentially equal list-assignments: L(w)=\{1,\dots,\Delta\} for some w , and L(v)=\{1,\dots,\Delta+1\} for all other v . Note also that the examples in the proof of Lemma 25 have connectivity 1 . In fact, we don’t know how to construct examples with larger connectivity, which raises the following question. Question 26 . Can the Main Theorem be extended to k -connected graphs, if at most k-1 vertices v have lists with size smaller than \deg(v)+1 ? One observation that supports such an extension is the following. Suppose that G is a k -connected graph with a list-assignment L such that |L(w)|\leq\deg(w) for at most k-1 vertices w\in V(G) , and |L(v)|\geq\deg(v)+1 for all other v\in V(G) . Then if we remove the vertices with small lists, the remaining graph is a connected graph satisfying the condition in the Main Theorem, but it is not obvious what this means for the structure of \mathcal{C}(G,L) . Another possible strengthening of our main results involves reducing the upper bound of the diameter of the L -recolouring graph. Since the diameter \diam(\mathcal{C}(P_{n},3)) of the 3 -recolouring graph of the path P_{n} is \Theta(n^{2}) , a quadratic bound is best possible in general. However, is the presence of long induced paths of degree- 2 vertices necessary for the L -recolouring graph to have such a large diameter? We propose the following conjectures. Conjecture 27 . Let G be a connected graph with n vertices, and let L be a list-assignment of G . (a) If, in addition to the conditions in the Key Lemma, G has minimum degree at least 3 , then \mathcal{C}(G,L) is connected and has diameter O(n) . (b) If, in addition to the conditions in the Main Theorem, G has minimum degree at least 3 , then \widehat{\mathcal{C}}(G,L) is connected and has diameter O(n) . (c) If, in addition to the conditions in the Main Theorem, G has no path of degree- 2 vertices of length more than t for some t\geq 0 , then \widehat{\mathcal{C}}(G,L) is connected and has diameter O((t+1)n) . Regarding Conjecture (a) (a), note that Lemma 8 provides a bound on the diameter of order \overline{d}n , where \overline{d} is the average degree. As a first step towards part (b) of the conjecture, recall the result of Bousquet et al. [ 5 ] that \diam(\mathcal{C}(G,\Delta))\leq f(\Delta)\cdot n for standard colouring. But their function f is superexponential in \Delta , so proving part (b) for standard colouring would already be a significant improvement over what is known. 5.1 Correspondence Colouring As alluded to earlier, in most of our arguments towards the Key Lemma and the Main Theorem, it is not so relevant which specific colours are present in which list. More relevant are the specific list-sizes as compared to their respective vertices’ degrees. To what extent are the colours themselves essential to the Main Results? This question leads us naturally to a strengthened notion, one that has been intensively studied in chromatic graph theory in recent years, called correspondence colouring (also called DP-colouring) [ 15 ] . In this closing part of the paper, we discuss how we might be able (or not) to extend our results to this more general context. To introduce the notion informally, suppose that we think of list colouring as ordinary colouring but under some adversarial choice of worst-case assignments of colour-lists at each vertex. Analogously, correspondence colouring can be thought of as giving our adversaries even more power by letting them choose worst-case matchings of ‘colours’ between the lists of adjacent vertices — any pair of matched ‘colours’ may not be used simultaneously in order for the colouring to be ‘proper’. There are various equivalent definitions and notations, so we fix our formalisms for correspondence colouring as follows. A ( correspondence -) cover of a graph G is a pair (L,H) , where H is a graph and L:V(G)\to 2^{V(H)} are such that the following hold: \bullet the sets \{L(v):v\in V(G)\} partition V(H) ; \bullet if there is an edge in H between L(u) and L(v) , then uv is an edge of G ; \bullet for any v\in V(G) , L(v) induces a clique in H ; \bullet for any u,v\in V(G) , the bipartite subgraph of H induced between L(u) and L(v) is a matching. (A cover is analogous to a list-assignment L .) Given k:V(G)\to\mathbb{N} , we call the cover k -fold if |L(v)|\geq k(v) for all v\in V(G) . (This is analogous to a lower bound condition on the list-sizes for L .) An (L,H) -colouring is an independent set of H of size |V(G)| . (This is analogous to a proper L -colouring.) Many prominent results for list colouring have been generalised to correspondence colouring as well. But as our next example shows, this fails for our Main Theorem, even for cliques. Example 28 . Denote the vertices of K_{n} by v_{1},\ldots,v_{n} . Form the cover graph (L,H) by connecting (v_{i},k) and (v_{j},\ell) for every i\neq j if and only if k=\ell\in\{3,\ldots,n\} or k=1,\ell=2 or k=2,\ell=1 . That is, using a colour on a vertex forbids that same colour on each neighbour, except for colours 1 and 2. Using colour 1 on any vertex forbids 2 on its neighbours, and vice versa. Now \mathcal{C}(K_{n},(L,H)) has exactly two large components. Proof. By the pigeonhole principle, every (L,H) -colouring of K_{n} has at least two vertices coloured with 1 or 2 (and these must be the same colour). So we have two components (with no frozen colourings), one containing the ‘all 1’ colouring, and one containing the ‘all 2’ colouring. ∎ Being a bit more precise, we can find n-2 exceptions. Starting from a ‘straight’ cover graph of K_{n} with lists of size n , we ‘twist’ 1 and 2 on each edge in a subclique K_{q} for some q\in\{2,\ldots,n-1\} . (Note that we get isomorphic cover graphs by letting q=n-1 or q=n .) Example 29 . Denote the vertices of K_{n} by v_{1},\ldots,v_{n} . For a value q\in\{2,\ldots,n-1\} , form the cover graph (L,H) by connecting (v_{i},k) and (v_{j},\ell) exactly when either \bullet k=\ell and k\in\{3,\ldots,n\} ; or \bullet \max\{i,j\}\leq q and \{k,\ell\}=\{1,2\} ; or \bullet \max\{i,j\}>q and k=\ell . Then \mathcal{C}(K_{n},(L,H)) has exactly two non-singleton components (as well as many frozen colourings if qq , is coloured by 3-i and one cannot recolour v_{j} . In this case, the only valid recolouring step is to recolour \alpha(v_{\ell}) with i for some \ell\in\{1,\ldots,q\}\setminus\{j\} . Thus A_{1} and A_{2} are not connected. ∎ For n=4 , in addition to the cases q=2 and q=3 in Example 29 , we discovered a third 4 -fold correspondence-cover of K_{4} for which \mathcal{C}(K_{n},(L,H)) has two non-singleton components. Denote the vertices of K_{4} by v_{1},\ldots,v_{4} . The cover graph (L,H) is depicted in Fig. 4 . It has L(v_{i})=\{(v_{i},j):j\in\{1,2,3,4\}\} for every i\in\{1,2,3,4\} , and is obtained by adding the five edges \{\,((v_{1},0),(v_{2},1)),\,((v_{1},1),(v_{2},0)),\,((v_{2},0),(v_{3},2)),\,((v_{2},2),(v_{3},3)),\,((v_{2},3),(v_{3},0))\,\}, and the straight edges (edges of the form (v_{h},j),(v_{i},j) for i\not=h ) elsewhere such that every two lists L(v_{i}) and L(v_{h}) span a perfect matching. Now \mathcal{C}(K_{n},(L,H)) has exactly two non-singleton components (each containing 24 (L,H) -colourings). The cover graph is obtained from the Möbius-Kantor graph, superimposed with the four list-cliques. By computer we verified that for no other 4 -fold cover graphs does \mathcal{C}(K_{4},(L,H)) have multiple non-singleton components. Those examples above suggests that a precise characterisation of ‘bad’ cover graphs for K_{n} may be hard. Figure 4 : A 4 -fold correspondence-cover (L,H) of K_{4} for which \widehat{\mathcal{C}}(K_{4},(L,H)) is not connected. Despite the previous examples, we remark that the Key Lemma does hold for correspondence colouring, with a slightly modified proof. In the proof of Lemma 5 , the bad neighbours need not form an independent set. So when we recolour w to unfreeze the frozen bad neighbours, and recolour the first bad neighbour, this could possibly freeze another bad neighbour. Fortunately, if v has at least two bad neighbours, then v is unfrozen (even for correspondence) so we can recolour v to unfreeze its bad neighbours. (We also handle these bad neighbours of w in order of non-increasing distance from v , to avoid undoing progress that we made previously.) We may need a few more steps than for the list colouring case, but some version of the lemma still holds. We don’t have a good idea of what results might be possible for correspondence colouring, similar to those for list colouring. So to conclude the paper, we pose a few questions that might lead us to a better understanding. Question 30 . (a) What characterises the ‘bad’ covers of the clique K_{n} ? When n=3 we have only three non-isomorphic covers, one of which is equivalent to the case of standard colouring. Exactly one of these is bad. When n=4 we have 75 non-isomorphic covers; a computer search showed that exactly three are bad. (b) What is the best possible diameter bound for the Key Lemma with correspondence colouring? Is it O(n) (as we conjecture for list colouring in Conjecture 27 (a))? (c) Does some version of the Main Theorem hold for correspondence colouring, possibly with additional well-understood exceptional graphs? Open access statement For the purpose of open access, a CC BY public copyright license is applied to any Author Accepted Manuscript (AAM) arising from this submission.