Graph Coloring Reconfiguration Department of Mathematics and Statistics Seminar (November 2024)

Department of Mathematics and Statistics Seminar | Graph Coloring Reconfiguration

Abstract: Reconfiguration is the concept of moving between different states of a system by transforming one state into another using some prescribed transformation rule (move). 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 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. Las Vergnas and Meyniel showed that if a graph is (k − 1)- degenerate, then each pair of its k-colorings are k-equivalent. Mohar conjectured the same conclusion for connected k-regular graphs. This was proved by Feghali, Johnson, and Paulusma for k = 3 (with a single exception K2 K3) and for k ≥ 4, by Bonamy, Bousquet, Feghali and Johnson.

We prove an analogous result for list-coloring. 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 L-valid Kempe swaps. 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 (again with a single exception K2 K3). The proof relies on the following key lemma.

Let H be a graph such that for every degree-assignment LH all LH-colorings are LH- equivalent. If G is a connected graph that contains H as an induced subgraph, then for every degree-assignment LG for G all LG-colorings are LG-equivalent.

About the speaker
Dr. Reem Mahmoud, NYU-Abu Dhabi, 

For more information, please contact Cristian Enache | [email protected].