Coloring Reconfiguration under Color Swapping

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

Read Coloring Reconfiguration under Color Swapping by Janosch Fuchs, Rin Saito, Tatsuhiro Suga, Takahiro Suzuki, Yuma Tamura (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-06473.txt.

Description

Janosch Fuchs and co-authors add a new move to the coloring reconfiguration problem. Given two proper colorings of a graph, can one be reshaped into the other through legal intermediate colorings? The new rule, color swapping, lets two neighboring vertices exchange colors whenever the result stays proper, a move unlike the single-vertex and Kempe chain rules studied before.

Complexity splits cleanly at three colors: swapping is solvable in polynomial time for at most two colors and becomes PSPACE-complete from three colors up. Hardness survives even on bipartite, split, and bounded-degree planar graphs. Polynomial algorithms do exist for paths with three colors, split graphs with fixed colors, and cographs with any number of colors.

Catalog record

CREATORJanosch Fuchs, Rin Saito, Tatsuhiro Suga, Takahiro Suzuki, Yuma Tamura
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE100 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-06473

Browse the full library · About the Tower of Babel