Shortest Reconfiguration of Colorings Under Kempe Changes

DOI10.4230/LIPICS.STACS.2020.35MaRDI QIDQ5874308zbMATH OpenOpenAlexFDO

Authors Marthe Bonamy, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Moritz Mühlenthaler, Akira Suzuki, Kunihiro Wasa

Publication date 7 February 2023

Full work available at URL https://hal.archives-ouvertes.fr/hal-02527059

zbMATH Keywords

combinatorial reconfigurationgraph algorithmsgraph coloringKempe equivalence

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cited in

(3)

• Kempe equivalence of 4‐critical planar graphs
• Gap preserving reductions between reconfiguration problems
• Optimal PSPACE-hardness of approximating set cover reconfiguration

This page was built for publication: Shortest Reconfiguration of Colorings Under Kempe Changes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5874308)