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

zbMATH Keywords

graph coloringPSPACE-completenesscombinatorial reconfiguration

Mathematics Subject Classification ID

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)

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

Cites Work

• A dichotomy theorem for circular colouring reconfiguration
• A reconfigurations analogue of Brooks' theorem and its consequences
• Finding paths between 3-colorings
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Finding shortest paths between graph colourings
• Homomorphism reconfiguration via homotopy
• Linear-time algorithm for sliding tokens on trees
• On the complexity of reconfiguration problems
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
• Reconfiguration of cliques in a graph
• Relationships between nondeterministic and deterministic tape complexities
• The complexity of bounded length graph recoloring and CSP reconfiguration
• The complexity of change
• The list coloring reconfiguration problem for bounded pathwidth graphs

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)