{"ID":2844434,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.06473","arxiv_id":"2511.06473","title":"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 \\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.","short_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...","url_abs":"https://arxiv.org/abs/2511.06473","url_pdf":"https://arxiv.org/pdf/2511.06473v1","authors":"[\"Janosch Fuchs\",\"Rin Saito\",\"Tatsuhiro Suga\",\"Takahiro Suzuki\",\"Yuma Tamura\"]","published":"2025-11-09T17:36:34Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}