The complexity trichotomy for circular-colouring mixing
The complexity trichotomy for circular-colouring mixing
Let denote the graph used as the target for -colourings, and let the textsc{G_{p,q}}-Mixing problem ask whether the reconfiguration graph of -colourings of an input graph is connected. Circular-colouring mixing complexity conjecture. If
then \textsc{G_{p,q}}-Mixing is in P; if
then it is co-NP-complete; and if
then it is PSPACE-complete. The first two cases extend known complexity results for odd-cycle mixing and planar inputs, while the full classification remains open, particularly the PSPACE-completeness claim for ratios at least .
Sources & referencesView supporting material
Primary source
Richard C. Brewster and Benjamin Moore, “Characterizing Circular Colouring Mixing for pq<4”, arXiv:2008.12185 (2022).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.