2015/08/23 by Brewster, Richard C., McGuinness, Sean, Moore, Benjamin +1 · 1 citation
#05C15 #05C85 #68Q17 #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1508.05573
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≤ p/q <4 and is PSPACE-complete for p/q≥ 4. This generalizes a known dichotomy theorem for reconfiguring classical graph colourings.