PreprintarXiv licencearXiv
Degree-list Kempe equivalence for 3-connected graphs
Abstract
In a proper coloring, a Kempe change interchanges two colors on a connected component of the subgraph they induce. For a fixed list assignment L, a Kempe change is L-valid if it transforms an L-coloring into another L-coloring. We prove that if G is a $3$-connected graph other than a complete graph or the triangular prism, and L is a list assignment with |L(v)|≥ dG(v) for every vertex v, then G has a proper L-coloring and any two such colorings can be transformed into one another by a finite sequence of L-valid Kempe changes. This proves a conjecture of Chakraborty, Feghali and Mahmoud.
Related
- Degree sequences of spectrally extremal connected nonregular graphs with prescribed maximum degree: the dense case
- Perfect matchings in planar 3-connected graphs: girth five and minimum degree five
- On the maximally edge-connected square graphs with degree sequence conditions
- When chromatic polynomials coincide with list-color functions: a threshold linear in the maximum degree
- On the Equivalence of Stochastic Control and Path Space Formulations for Schrödinger Bridges over Compact Connected Lie Groups
BibTeX
@misc{wang2026degreelist,
title = {{Degree-list Kempe equivalence for 3-connected graphs}},
author = {Hongyang Wang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.35701},
eprint = {2610.35701},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.35701},
}
RIS
TY - UNPB
TI - Degree-list Kempe equivalence for 3-connected graphs
AU - Hongyang Wang
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2610.35701
UR - https://arxiv.org/abs/2610.35701
AB - In a proper coloring, a Kempe change interchanges two colors on a connected component of the subgraph they induce. For a fixed list assignment L, a Kempe change is L-valid if it transforms an L-coloring into another L-coloring. We prove that if G is a $3$-connected graph other than a complete graph or the triangular prism, and L is a list assignment with |L(v)|≥ d_G(v) for every vertex v, then G has a proper L-coloring and any two such colorings can be transformed into one another by a finite sequence of L-valid Kempe changes. This proves a conjecture of Chakraborty, Feghali and Mahmoud.
ER -