## 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