DMS Combinatorics Seminar

Speaker: Dan Cranston (Virginia Commonwealth University) 

Title: Kempe Equivalent List Colorings

Abstract: An $\alpha,\beta$-Kempe swap in a properly colored graph interchanges the colors on some component of the subgraph induced by colors $\alpha$ and $\beta$. Two $k$-colorings of a graph are $k$-Kempe equivalent if we can form one from the other by a sequence of Kempe swaps (never using more than $k$ colors). Las Vergnas and Meyniel showed that if a graph is $(k-1)$-degenerate, then each pair of its $k$-colorings are $k$-Kempe equivalent. Mohar conjectured the same conclusion for connected $k$-regular graphs. This was proved for $k=3$ by Feghali, Johnson, and Paulusma (with a single exception $K_2\dbox K_3$, also called the 3-prism) and for $k\ge 4$ by Bonamy, Bousquet, Feghali, and Johnson.

In this paper we prove an analogous result for list-coloring. For a list-assignment $L$ and an $L$-coloring $\vph$, a Kempe swap is called $L$-valid for $\vph$ 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\ge 3$. We prove that if $(L)$ is a $k$-assignment, then all $L$-colorings are $L$-equivalent (again excluding only $K_2\box K_3$. When $(k\ge 4$, the proof is completely self-contained, implying an alternate proof of the result of Bonamy et al.

This is joint work with Reem Mahmoud.