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 \leq 2$, and is PSPACE-complete for $k \geq 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.

翻译：在\\textsc{着色重构}问题中，给定图的两个合法$k$-着色，要求判定是否可以通过反复应用指定的重着色规则，在始终保持合法着色的前提下，将其中一个着色转换为另一个。针对该问题，已有两种重着色规则被广泛研究：\\emph{单顶点重着色}与\\emph{Kempe链重着色}。本文引入一种称为\\emph{颜色交换}的新规则，允许相邻顶点交换颜色并保持着色合法性，进而研究该规则下问题的计算复杂性。我们首先建立了关于$k$的复杂性二分：当$k \\leq 2$时问题可在多项式时间内求解，而当$k \\geq 3$时为PSPACE完全问题。进一步证明即使在受限图类（包括二分图、分裂图和有界度平面图）上问题仍保持PSPACE完全性。与之相对，我们针对若干图类提出了多项式时间算法：当$k=3$时的路径图、固定$k$时的分裂图，以及任意$k$时的补图。