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
| CREATOR | Janosch Fuchs, Rin Saito, Tatsuhiro Suga, Takahiro Suzuki, Yuma Tamura |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 100 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-06473