## Defense Date

2024

## Document Type

Dissertation

## Degree Name

Doctor of Philosophy

## Department

Computer Science

## First Advisor

Daniel Cranston

## Abstract

*Reconfiguration* is the concept of moving between different solutions to a problem by transforming one solution into another using some prescribed transformation rule (move). Given two solutions s_{1} and s_{2} of a problem, reconfiguration asks whether there exists a sequence of moves which transforms s_{1} into s_{2}. Reconfiguration is an area of research with many contributions towards various fields such as mathematics and computer science.

The *k-coloring reconfiguration* problem asks whether there exists a sequence of moves which transforms one k-coloring of a graph G into another. A move in this case is a type of *Kempe swap*. An *α, β-Kempe swap* in a properly colored graph interchanges the colors on some component of the subgraph induced by vertices colored α and β. Two k-colorings of a graph are *k-equivalent* if we can form one from the other by a sequence of Kempe swaps (never using more than k colors). The k-coloring reconfiguration problem has applications in statistical physics and mechanics; in particular, it has positive implications on the Markov chains defined for the Ising model in statistical physics and the antiferromagnetic Pott’s model in statistical mechanics.

The reconfiguration graph C_{k}(G) associated with the k-coloring reconfiguration problem is defined as follows: The vertices of C_{k}(G) are the k-colorings of G and two vertices in C_{k}(G) are adjacent if their corresponding k-colorings differ by a single move. We study C_{k}(G) for certain classes of graphs G. In particular, we study the connectedness and the diameter of C_{k}(G). Indeed, C_{k}(G) being connected is equivalent to the k-colorings of G being pairwise k-equivalent. On the other hand, the diameter of C_{k}(G) is d if and only if for every two k-colorings of G, there is a sequence of length at most d from one to the other. Our results on the connectedness of C_{k}(G) imply the Markov chain for the models mentioned above is ergodic, while lower bound results on the diameter of C_{k}(G) imply lower bounds on the mixing time of the Markov chain. It is conjectured that the diameter of C_{k}(G) is O(n^{2}) for every d-degenerate graph G whenever k ≥ d + 2. As a step towards proving this conjecture for triangle-free planar graphs, we show that C_{5}(G) is O(n^{2}) for every planar graph G with no 3-cycles and no 5-cycles. Moreover, we study the connectedness of C_{5}(G) for the *triangulated toroidal grid*, G := T [m × n], which is formed from (a toroidal embedding of) the Cartesian product of C_{m} and C_{n} by adding parallel diagonals inside all 4-faces. We prove that all 5-colorings of T [m × n] are 5-equivalent when m, n ≥ 6, i.e., C_{5}(G) is connected for such toroidal graphs G. We also explore list-coloring reconfiguration. For a list-assignment L and an L-coloring φ, a Kempe swap is called *L-valid* for φ if performing the Kempe swap yields another L-coloring. Two L-colorings are called *L-equivalent* if we can form one from the other by a sequence of a type of L-valid Kempe swaps. The associated reconfiguration graph in this case is C_{L}(G). Let G be a connected k-regular graph with k ≥ 3. We prove that if L is a k-assignment, then all L-colorings are L-equivalent unless G is the 3-prism, i.e., C_{L}(G) is connected for every k-assignment L. This generalizes an analogous result about the k-colorings of k-regular graphs.

## Rights

© The Author

## Is Part Of

VCU University Archives

## Is Part Of

VCU Theses and Dissertations

## Date of Submission

4-15-2024