A dichotomy theorem for circular colouring reconfiguration

Let p and q   be positive integers with p/q≥2p/q≥2. The “reconfiguration problem” for circular colourings asks, given two (p,q)(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)(p,q)-colouring? We show that this problem can be solved in polynomial time for 2≤p/q<42≤p/q<4 and that it is PSPACE-complete for p/q≥4p/q≥4. This generalizes a known dichotomy theorem for reconfiguring classical graph colourings. As an application of the reconfiguration algorithm, we show that graphs with fewer than (k−1)!/2(k−1)!/2 cycles of length divisible by k are k-colourable.