14:00
15:00

/Exposé en anglais/Talk in english/

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.

[Daniel Cranston] (Université de Lyon)
https://www.people.vcu.edu/~dcranston/

Remarks / Remarques

Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .

https://webconf.u-bordeaux.fr/b/mar-ef4-zed and room 178/LaBRI