Kempe changes in degenerate graphs

We consider Kempe changes on the k-colorings of a graph on n vertices. If the graph is (k-1)-degenerate, then all its k-colorings are equivalent up to Kempe changes. However, the sequence between two k-colorings that arises from the proof may have length exponential in the number of vertices. An intriguing open question is whether it can be turned polynomial. We prove this to be possible under the stronger assumption that the graph has treewidth at most k - 1. Namely, any two k-colorings are equivalent up to O(kn2) Kempe changes. We investigate other restrictions (list coloring, bounded maximum average degree, degree bounds). As one of the main results, we derive that given an n-vertex graph with maximum degree triangle, the triangle-colorings are all equivalent up to O triangle(n2) Kempe changes, unless triangle = 3 and some connected component is a 3-prism, that is K2 square K3, in which case there exist some non-equivalent 3-colorings. (c) 2023 Elsevier Ltd. All rights reserved.