Pith. sign in

REVIEW 1 cited by

A Note on the Complexity of Graph Recoloring

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

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

arxiv 2401.03011 v1 pith:R4PVQYMH submitted 2024-01-05 math.CO cs.DM

Nicolas Bousquet This is my paper · ORCID
classification math.COcs.DM
keywords graphmixingcoloringalongcasecerecedaco-np-completeco-np-hard
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
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.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Optimal PSPACE-hardness of Approximating $q$-CSP Reconfiguration

    cs.CC 2026-07 accept novelty 7.5 of 10

    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.

Pith tools