PSPACE-completeness conjecture for 4-To-3 recoloring
PSPACE-completeness conjecture for 4-To-3 recoloring
Let be a graph. A -To- instance asks whether a proper -coloring of can be transformed into a proper -coloring by repeatedly recoloring one vertex while maintaining a proper coloring. The 4-To-3 conjecture. -To- 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
Sign in to submit a solution.
No solutions have been posted yet.