A Dichotomy Theorem for Circular Colouring Reconfiguration

Abstract

The "reconfiguration problem" for circular colourings asks, given two $(p,q)$-colourings $f$ and $g$ of a graph $G$, is it possible to transform $f$ into $g$ by changing the colour of one vertex at a time such that every intermediate mapping is a $(p,q)$-colouring? We show that this problem can be solved in polynomial time for $2\le p/q<4$ and is PSPACE-complete for $p/q\ge 4$. This generalizes a known dichotomy theorem for reconfiguring classical graph colourings.

22 pages, 5 figures