Complexity of coloring reconfiguration under recolorability constraints

DOI10.4230/LIPICS.ISAAC.2017.62MaRDI QIDQ5136283zbMATHOpenAlexFDO

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)

• Homomorphism reconfiguration via homotopy
• Using contracted solution graphs for solving reconfiguration problems
• Tight Lower and Upper Bounds for the Complexity of Canonical Colour Refinement
• Graph homomorphism reconfiguration and frozen \(H\)-colorings
• Recoloring some hereditary graph classes
• The coloring reconfiguration problem on specific graph classes
• The algorithmic complexity of colour switching
• The complexity of changing colourings with bounded maximum degree
• Parameterized complexity of optimizing list vertex-coloring through reconfiguration
• Block symmetries in graph coloring reconfiguration systems
• Using contracted solution graphs for solving reconfiguration problems
• Between Colorings and Layouts - Minimum Morphism Cost Problems
• Homomorphism reconfiguration via homotopy
• The complexity of bounded length graph recoloring and CSP reconfiguration
• Making Role Assignment Feasible: A Polynomial-Time Algorithm for Computing Ecological Colorings
• Algorithms for Coloring Reconfiguration Under Recolorability Constraints
• Tight lower and upper bounds for the complexity of canonical colour refinement

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)