REVIEW 1 cited by
A Note on the Complexity of Graph Recoloring
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
abstract
We say that a graph is $k$-mixing if it is possible to transform any $k$-coloring into any other via a sequence of single vertex recolorings keeping a proper coloring all along. Cereceda, van den Heuvel and Johnson proved that deciding if a graph is $3$-mixing is co-NP-complete and left open the case $k \ge 4$. We prove that for every $k \ge 4$, $k$-mixing is co-NP-hard.
Forward citations
Cited by 1 Pith paper
-
Optimal PSPACE-hardness of Approximating $q$-CSP Reconfiguration
Maxmin q-CSP Reconfiguration is PSPACE-hard to approximate within 1/2^{q-1}+ε, while a (1/2^{q-1}-ε)-factor is in NP under perfect completeness, optimally under NP≠PSPACE.
Discussion (0). Continue with ORCID to comment.