SCIENCE@home

Coloring Reconfiguration Under Color Swapping

Janosch Fuchs,Rin Saito,Tatsuhiro Suga,Takahiro Suzuki,Yuma Tamura

Published 2025 in International Symposium on Algorithms and Computation

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.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-37 of 37 references · Page 1 of 1

CITED BY

  • No citing papers are available for this paper.

Showing 0-0 of 0 citing papers · Page 1 of 1