Algorithms for Coloring Reconfiguration Under Recolorability Constraints

DOI10.4230/LIPIcs.ISAAC.2018.37OpenAlexW2908478485MaRDI QIDQ5091029

Takehiro Ito, Xiao Zhou, Hiroki Osawa, Akira Suzuki

Publication date: 21 July 2022

Full work available at URL: https://doi.org/10.4230/lipics.isaac.2018.37

zbMATH Keywords

graph algorithmgraph coloringcombinatorial reconfiguration

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites Work

• A dichotomy theorem for circular colouring reconfiguration
• Finding shortest paths between graph colourings
• On the complexity of reconfiguration problems
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Parameterized complexity of the list coloring reconfiguration problem with graph parameters
• Reconfiguration in bounded bandwidth and tree-depth
• Recoloring graphs via tree decompositions
• Introduction to reconfiguration
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
• The complexity of change
• The List Coloring Reconfiguration Problem for Bounded Pathwidth Graphs
• The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration
• Homomorphism reconfiguration via homotopy
• Finding paths between 3-colorings
• Using contracted solution graphs for solving reconfiguration problems.
• Complexity of Coloring Reconfiguration under Recolorability Constraints

This page was built for publication: Algorithms for Coloring Reconfiguration Under Recolorability Constraints