# Introduction to Reconfiguration
## 6 Connectivity and Diameter for \(k\)-Coloring
### Variants of Coloring  
We first consider an alternate choice of reconfiguration step, and then consider related problems using coloring. Instead of recoloring a single vertex at one step, a _Kempe change_, introduced by [PERSON] in his attempted proof of the Four Color Theorem [89], consists of exchanging the colors of all vertices in a connected component in the subgraph induced on vertices using a particular pair of colors. Such recolorings have been used in the proof of the Five Color Theorem, Vizing's Edge-Coloring Theorem, in theoretical physics, and in the determination of timetables [90].  
The reconfiguration graph under Kempe changes is connected for the following cases: \(k=4\) for Eulerian triangulation of the plane [91], \(k=5\) for planar graphs [92], generalized to \(k\geq\chi(G)\) for planar graphs [93] and \(k=5\) for \(K_{5}\)-minor free graphs [94], and all colorings of a perfectly contractile graph [95]. Edge-coloring has also been considered under the same reconfiguration rule [93; 96; 97].  
When restricted to \(k\)-regular graphs, [PERSON] conjectured that the reconfiguration graph is connected for \(k\geq 3\), except when the instance is a clique on \(k+1\) vertices [93], and although it was shown to be false for \(k=3\) for the triangular prism [14], further investigations have focused on finding cases in which it holds. The conjecture was proved for \(k\geq 4\)[98], and eventually it was shown that the triangular prism and \(K_{3}\) are the only 3-regular graphs for which the reconfiguration graph for \(k=3\) is not connected [99].  
In List Coloring Reconfiguration[35], a generalization of \(k\)-Coloring Reconfiguration, each vertex \(v\) is supplied with a list \(L(v)\) of allowable colors. Early results in the area were obtained by generalizing results on \(k\)-Coloring Reconfiguration: the polynomial-time reachability algorithm for \(k\leq 3\) can be extended to this variant [32], and the reconfiguration graph is connected when the size of each list is at least \(\mathrm{col}(G)+2\)[83]. The reachability problem for List Coloring Reconfiguration has been shown to be PSPACE-complete for graphs of bounded bandwidth [47] as well as for complete split graphs (with modular-width zero) [44], and to be \(W[1]\)-hard parameterized by size of minimum vertex cover [75]. Fixed-parameter algorithms have been found when parameterized by \(k+\ell\) (where \(\ell\) is the length of the reconfiguration sequence) [79; 87], parameterized by \(k\) and modular-width of the input graph (and hence for cographs when parameterized by \(k\)) [75], and for shortest transformation, parameterized by \(k\) and the size of the minimum vertex cover (and hence for split graphsparameterized by \(k\)) [75]. Other variants for which reconfiguration has been studied include List Edge-Coloring[36; 40; 100], List(2,1)-Labeling[37], Circular Coloring[101; 102], Acyclic Coloring[103], and Equitable Coloring[103]. The problem of \(k\)-Coloring Reconfiguration can also be seen as a special case of Homomorphism Reconfiguration[101; 104] and Constraint Satisfaction Reconfiguration (Section 8).