Abstract
A Kempe chain on colors (Formula presented.) and (Formula presented.) is a component of the subgraph induced by colors (Formula presented.) and (Formula presented.). A Kempe change is the operation of interchanging the colors of some Kempe chains. For a list-assignment (Formula presented.) and an (Formula presented.) -coloring (Formula presented.), a Kempe change is (Formula presented.) -valid for (Formula presented.) if performing the Kempe change yields another (Formula presented.) -coloring. Two (Formula presented.) -colorings are (Formula presented.) -equivalent if we can form one from the other by a sequence of (Formula presented.) -valid Kempe changes. A degree-assignment is a list-assignment (Formula presented.) such that (Formula presented.) for every (Formula presented.). Cranston and Mahmoud asked: For which graphs (Formula presented.) and degree-assignment (Formula presented.) of (Formula presented.) is it true that all the (Formula presented.) -colorings of (Formula presented.) are (Formula presented.) -equivalent? We prove that for every 4-connected graph (Formula presented.) which is not complete and every degree-assignment (Formula presented.) of (Formula presented.), all (Formula presented.) -colorings of (Formula presented.) are (Formula presented.) -equivalent.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 410-418 |
| Number of pages | 9 |
| Journal | Journal of Graph Theory |
| Volume | 107 |
| Issue number | 2 |
| DOIs | |
| State | Published - Oct 2024 |
Keywords
- graph coloring
- kempe change
- reconfiguration
ASJC Scopus subject areas
- Geometry and Topology
- Discrete Mathematics and Combinatorics