Kempe reachability with three or more colors is hard on claw-free graphs
Kempe Reachability with $k\geq 3$ Colors Is $\mathsf{PSPACE}$-Complete on Claw-Free Graphs
Data Structures and AlgorithmsDiscrete Mathematics
Summary
This paper studies a puzzle about changing colors of graph vertices step by step without breaking color rules. The authors show that finding a sequence of valid color swaps to go from one coloring to another is computationally very hard (PSPACE-complete) even on special kinds of graphs called claw-free graphs. This settles the problem’s difficulty in a more restricted setting than was known before. Their result also applies to edge-coloring versions in certain regular graphs.
What this means in practice
- •For graph algorithm designers: Know that deciding color transformation sequences is hard even on claw-free graphs, guiding algorithm design and complexity expectations.
- •For network schedulers: Use the hardness result to understand limits on reconfiguring resource assignments in networks modeled by claw-free graphs.
A theory result. No direct application yet.
Authors
Duc A. Hoang
Abstract
A \emph{proper vertex coloring} assigns colors to vertices so that adjacent vertices have distinct colors. A \emph{Kempe change} in a proper vertex coloring exchanges two colors on one component of the subgraph induced by the vertices of those colors. For a fixed palette of $k$ colors, \textsc{Kempe Reachability} asks whether two given proper vertex colorings of the same graph are connected by a sequence of Kempe changes. This problem is known to be $\mathsf{PSPACE}$-complete for every fixed $k\geq 3$. A graph is \emph{claw-free} if no vertex has three pairwise nonadjacent neighbors. The \emph{line graph} of a graph has one vertex for each edge, with two vertices adjacent exactly when the corresponding edges share an end. Line graphs are claw-free, and their Kempe changes correspond to \emph{edge-Kempe changes} in the original graph, which exchange two colors on one component of the subgraph formed by the edges of those colors. A claw-free graph with a proper $k$-coloring has maximum degree at most $2k-2$, whereas for $k\geq 4$ all proper $k$-colorings of a graph of maximum degree at most $k$ are connected by Kempe changes. We show that, for every fixed $k\geq 3$, \textsc{Kempe Reachability} with $k$ colors is $\mathsf{PSPACE}$-complete even on line graphs of connected simple $k$-regular graphs, and hence even on connected $(2k-2)$-regular claw-free graphs. Equivalently, deciding whether two proper $k$-edge-colorings are connected by edge-Kempe changes is $\mathsf{PSPACE}$-complete even on connected simple $k$-regular graphs. ChatGPT 6 Pro and Claude Fable 5.1 were used to assist with developing and reviewing mathematical arguments and drafting and revising the paper. The author takes full responsibility for the correctness and content of the paper.