Complexity of coloring reconfiguration under recolorability constraints
DOI10.4230/LIPICS.ISAAC.2017.62zbMATH Open1457.68224OpenAlexW2782559726MaRDI QIDQ5136283FDOQ5136283
Authors: Hiroki Osawa, Akira Suzuki, Takehiro Ito, Xiao Zhou 
Publication date: 25 November 2020
Full work available at URL: https://doi.org/10.4230/lipics.isaac.2017.62
Recommendations
- The coloring reconfiguration problem on specific graph classes
- The complexity of bounded length graph recoloring and CSP reconfiguration
- Homomorphism reconfiguration via homotopy
- A dichotomy theorem for circular colouring reconfiguration
- Finding Paths between Graph Colourings: Computational Complexity and Possible Distances
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15)
Cites Work
- Relationships between nondeterministic and deterministic tape complexities
- PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
- The complexity of change
- Finding paths between 3-colorings
- Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
- Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
- The complexity of bounded length graph recoloring and CSP reconfiguration
- Homomorphism reconfiguration via homotopy
- A dichotomy theorem for circular colouring reconfiguration
- Finding shortest paths between graph colourings
- On the complexity of reconfiguration problems
- Linear-time algorithm for sliding tokens on trees
- Reconfiguration of cliques in a graph
- The list coloring reconfiguration problem for bounded pathwidth graphs
- A reconfigurations analogue of Brooks' theorem and its consequences
Cited In (17)
- Graph homomorphism reconfiguration and frozen \(H\)-colorings
- Between Colorings and Layouts - Minimum Morphism Cost Problems
- Algorithms for Coloring Reconfiguration Under Recolorability Constraints
- Using contracted solution graphs for solving reconfiguration problems
- The complexity of changing colourings with bounded maximum degree
- Tight lower and upper bounds for the complexity of canonical colour refinement
- Parameterized complexity of optimizing list vertex-coloring through reconfiguration
- Block symmetries in graph coloring reconfiguration systems
- Homomorphism reconfiguration via homotopy
- Making Role Assignment Feasible: A Polynomial-Time Algorithm for Computing Ecological Colorings
- Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement
- The coloring reconfiguration problem on specific graph classes
- The complexity of bounded length graph recoloring and CSP reconfiguration
- Recoloring some hereditary graph classes
- The algorithmic complexity of colour switching
- Using contracted solution graphs for solving reconfiguration problems
- Homomorphism reconfiguration via homotopy
This page was built for publication: Complexity of coloring reconfiguration under recolorability constraints
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5136283)
