Coloring Reconfiguration under Color Swapping

Abstract

In the \textsc{Coloring Reconfiguration} problem, we are given two proper $k$-colorings of a graph and asked to decide whether one can be transformed into the other by repeatedly applying a specified recoloring rule, while maintaining a proper coloring throughout. For this problem, two recoloring rules have been widely studied: \emph{single-vertex recoloring} and \emph{Kempe chain recoloring}. In this paper, we introduce a new rule, called \emph{color swapping}, where two adjacent vertices may exchange their colors, so that the resulting coloring remains proper, and study the computational complexity of the problem under this rule. We first establish a complexity dichotomy with respect to $k$: the problem is solvable in polynomial time for $k\le 2$, and is PSPACE-complete for $k\ge 3$. We further show that the problem remains PSPACE-complete even on restricted graph classes, including bipartite graphs, split graphs, and planar graphs of bounded degree. In contrast, we present polynomial-time algorithms for several graph classes: for paths when $k=3$, for split graphs when $k$ is fixed, and for cographs when $k$ is arbitrary.

30 pages, 10 figures, ISAAC 2025