## Abstract

An α,β-Kempe swap in a properly colored graph interchanges the colors on some component of the subgraph induced by colors α and β. 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}□K_{3}, also called the 3-prism) and for k≥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 φ, 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 and G≠K_{k+1}. We prove that if L is a k-assignment, then all L-colorings are L-equivalent (again excluding only K_{2}□K_{3}). Further, if G∈{K_{k+1},K_{2}□K_{3}}, L is a Δ-assignment, but L is not identical everywhere, then all L-colorings of G are L-equivalent. When k≥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.

Original language | English (US) |
---|---|

Pages (from-to) | 125-153 |

Number of pages | 29 |

Journal | Combinatorica |

Volume | 44 |

Issue number | 1 |

DOIs | |

State | Published - Feb 2024 |

## Keywords

- 05C15
- 05C85
- Kempe swaps
- List-coloring
- Mohar’s Conjecture
- Reconfiguration

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Computational Mathematics