The complexity trichotomy for circular-colouring mixing

Let Gp,qG_{p,q} denote the graph used as the target for (p,q)(p,q)-colourings, and let the textsc{G_{p,q}}-Mixing problem ask whether the reconfiguration graph of (p,q)(p,q)-colourings of an input graph is connected. Circular-colouring mixing complexity conjecture. If

pq=2,\frac{p}{q}=2,

then \textsc{G_{p,q}}-Mixing is in P; if

2<pq<4,2<\frac{p}{q}<4,

then it is co-NP-complete; and if

pq4,\frac{p}{q}\geq 4,

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 44.

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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.