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.