On a problem of Cranston and Mahmoud

Dibyayan Chakraborty, Carl Feghali

Published 2022-11-30Version 1

A classical theorem of Gallai states that in every graph that is critical for $k$-colorings, the vertices of degree $k - 1$ induce a tree-like graph whose blocks are either complete graphs or cycles of odd length. Borodin and, independently, Erd\H{o}s et al. provided a well-known generalization of Gallai's Theorem to list colorings, where the list at each vertex has the same number of available colors as the degree of that vertex. In this paper, we obtain an analogous result for Kempe equivalence of list colorings, making substantial progress towards a problem of Cranston and Mahmoud.