2026-07-20T05:40:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24941 2026-02-09T08:02:21Z ddc:004 open_access

Coloring Reconfiguration Under Color Swapping Fuchs, Janosch Saito, Rin Suga, Tatsuhiro Suzuki, Takahiro Tamura, Yuma Combinatorial reconfiguration graph coloring PSPACE-complete graph algorithm In the 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: single-vertex recoloring and Kempe chain recoloring. In this paper, we introduce a new rule, called 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 ≤ 2, and is PSPACE-complete for k ≥ 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Janosch Fuchs and Rin Saito and Tatsuhiro Suga and Takahiro Suzuki and Yuma Tamura 2025 Is Part Of LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2025.33 urn:nbn:de:0030-drops-249411 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.33 eng https://creativecommons.org/licenses/by/4.0/legalcode