PSPACE-completeness conjecture for 4-To-3 recoloring

At least 1 year old · documented by

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.

References

Primary source

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

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.