# Introduction to Reconfiguration
## 6 Connectivity and Diameter for \(k\)-Coloring
### \(k\)-Coloring Reconfiguration  
To get a sense of the importance of the choice of \(k\) for connectivity and diameter, we consider both large and small values of \(k\). When \(k\) is sufficiently large, the reconfiguration graph is connected and has diameter linear in the number of vertices: each vertex is first recolored to a distinct color not used in either the source or target solution, and then is recolored to its target color. At the other extreme, consider an even cycle and \(k=2\); in this case, \(k\) is equal to \(\chi(G)\), the _chromatic number_ of \(G\) (the smallest number of colors for which it is possible to find a coloring of \(G\)); no vertex of the cycle can be recolored. Early results in the area focused on the difference between small and large values of \(k\), such as by showing that for \(2\leq\chi(G)\leq 3\), the reconfiguration graph is not connected for \(k=\chi(G)\)[31]. This left open the question of connectivity of bipartite graphs (\(\chi(G)=2\)) for \(k=3\); the yes-instances were characterized, and it was shown that the problem of deciding connectedness for bipartite graphs is coNP-complete, but restricted to planar bipartite graphs can be solved in polynomial time [78]. For \(k=3\), it was shown that the diameter is in \(O(|V(G)|^{2})\) for each connected component (and that this bound is tight, as there exist configurations at distance \(\Omega(|V(G)|^{2})\)), and that both reachability and shortest transformation can be solved in polynomial time [32]. In contrast, for \(k\geq 4\), there are both yes-instances and no-instances for connectivity [31], and there exists a family of graphs and a \(k\geq 4\) such that for every graph in the family there exist components of diameter superpolynomial in \(|V(G)|\)[35]. Moreover, for \(k\geq 4\), reachability is strongly NP-hard [79] and PSPACE-complete, even for bipartite graphs, planar graphs for \(4\leq k\leq 6\), and bipartite planar graphs for \(k=4\)[35]. We can consider the relationship between \(k\) and various properties of the instance, related to but distinct from the chromatic number. One choice is the maximum degree, \(\Delta(G)\), as it is known that the chromatic number of \(G\) is at most \(\Delta(G)\) unless \(G\) is a complete graph or a cycle with an odd number of vertices [80]. Recall that the degeneracy, \(\operatorname{col}(G)\), is the largest minimum degree of any subgraph of \(G\); the degeneracy of \(G\) is an upper bound on its maximum degree, and the treewidth of \(G\), \(tw(G)\), is an upper bound on \(\operatorname{col}(G)\). More precisely, for any connected graph that is not regular, \(\operatorname{col}(G)=\Delta(G)-1\)[81], and the chromatic number is at most one greater than the degeneracy. Yet another property of use is the _Grundy number_, \(\chi_{g}(G)\), defined as the largest possible number of colors used by a greedy coloring of \(G\); \(\chi_{g}(G)\leq\Delta(G)+1\). It has been shown that for every graph, the reconfiguration graph is connected when \(k\geq\Delta(G)+2\)[82], and in fact for \(k\geq\operatorname{col}(G)+2\)[83]. Investigations into _\(c\)-color-dense_ graphs proved that the reconfiguration graph is connected for chordal and chordal bipartite graphs [84], subsequently generalized to hold for any \(k\geq tw(G)+2\)[85] and \(k\geq\chi_{g}(G)+1\)[85]. So far, there are no known families where the reconfiguration graph is connected and of superpolynomial diameter; in fact, [PERSON] [77; 78] conjectured that for \(k\geq\operatorname{col}(G)+2\), the diameter of the reconfiguration graph is in \(O(|V(G)|^{2})\), and showed that the conjecture is true for the values\(k=1\) and \(k=\Delta(G)\)[77]. The results on connectivity also showed quadratic bounds on diameter, including a lower bound on diameter for chordal graphs, culminating in the proof of the conjecture for \(k\geq tw(G)+2\)[85].