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 s1 and s2 of a problem, reconfiguration asks whether there exists a sequence of moves which transforms s1 into s2. 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 Ck(G) associated with the k-coloring reconfiguration problem is defined as follows: The vertices of Ck(G) are the k-colorings of G and two vertices in Ck(G) are adjacent if their corresponding k-colorings differ by a single move. We study Ck(G) for certain classes of graphs G. In particular, we study the connectedness and the diameter of Ck(G). Indeed, Ck(G) being connected is equivalent to the k-colorings of G being pairwise k-equivalent. On the other hand, the diameter of Ck(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 Ck(G) imply the Markov chain for the models mentioned above is ergodic, while lower bound results on the diameter of Ck(G) imply lower bounds on the mixing time of the Markov chain. It is conjectured that the diameter of Ck(G) is O(n2) 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 C5(G) is O(n2) for every planar graph G with no 3-cycles and no 5-cycles. Moreover, we study the connectedness of C5(G) for the triangulated toroidal grid, G := T [m × n], which is formed from (a toroidal embedding of) the Cartesian product of Cm and Cn 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., C5(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 CL(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., CL(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