Back to Search
Start Over
Kempe Equivalent List Colorings.
- Source :
- Combinatorica; Feb2024, Vol. 44 Issue 1, p125-153, 29p
- Publication Year :
- 2024
-
Abstract
- An α , β -Kempe swap in a properly colored graph interchanges the colors on some component of the subgraph induced by colors α and β . 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 □ K 3 , also called the 3-prism) and for k ≥ 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 φ , a Kempe swap is called L-valid for φ 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 ≥ 3 and G ≠ K k + 1 . We prove that if L is a k-assignment, then all L-colorings are L-equivalent (again excluding only K 2 □ K 3 ). Further, if G ∈ { K k + 1 , K 2 □ K 3 } , L is a Δ -assignment, but L is not identical everywhere, then all L-colorings of G are L-equivalent. When k ≥ 4 , the proof is completely self-contained, implying an alternate proof of the result of Bonamy et al. Our proofs rely on the following key lemma, which may be of independent interest. Let H be a graph such that for every degree-assignment L H all L H -colorings are L H -equivalent. If G is a connected graph that contains H as an induced subgraph, then for every degree-assignment L G for G all L G -colorings are L G -equivalent. [ABSTRACT FROM AUTHOR]
- Subjects :
- GRAPH connectivity
GRAPH coloring
COLORS
COLORING matter
Subjects
Details
- Language :
- English
- ISSN :
- 02099683
- Volume :
- 44
- Issue :
- 1
- Database :
- Complementary Index
- Journal :
- Combinatorica
- Publication Type :
- Academic Journal
- Accession number :
- 175566088
- Full Text :
- https://doi.org/10.1007/s00493-023-00063-2