Kempe Equivalent List Colorings

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\square \,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 $$\varphi $$ , a Kempe swap is called L-valid for $$\varphi $$ 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$$ and $$G\ne K_{k+1}$$ . We prove that if L is a k-assignment, then all L-colorings are L-equivalent (again excluding only $$K_2\square \,K_3$$ ). Further, if $$G\in \{K_{k+1},K_2\square \,K_3\}$$ , L is a $$\Delta $$ -assignment, but L is not identical everywhere, then all L-colorings of G are L-equivalent. When $$k\ge 4$$ , the proof is completely self-contained, implying an alternate proof of the result of Bonamy et al. Our proofs rely on the following key lemma, which may be of independent interest. Let H be a graph such that for every degree-assignment $$L_H$$ all $$L_H$$ -colorings are $$L_H$$ -equivalent. If G is a connected graph that contains H as an induced subgraph, then for every degree-assignment $$L_G$$ for G all $$L_G$$ -colorings are $$L_G$$ -equivalent.