PSPACE-completeness conjecture for 4-To-3 recoloring

From papers

Let GG be a graph. A 44-To-33 instance asks whether a proper 44-coloring of GG can be transformed into a proper 33-coloring by repeatedly recoloring one vertex while maintaining a proper coloring. The 4-To-3 conjecture. 44-To-33 is PSPACE-complete. This is a more specific proposed complexity result for graph-coloring reconfiguration; the source presents it after discussing how PSPACE-completeness for restricted mixing problems would transfer to larger numbers of colors, and gives no resolution of the conjecture.

Progress summary

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

Sources & referencesView supporting material

Primary source

Nicolas Bousquet, “A Note on the Complexity of Graph Recoloring”, arXiv:2401.03011 (2024).

Solutions 0

No solutions have been posted yet.