Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances

DOI10.1016/J.TCS.2009.08.023zbMATH Open1177.05112OpenAlexW2036323482MaRDI QIDQ1034528FDOQ1034528

Authors: Paul Bonsma, Luis Cereceda 

Publication date: 6 November 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.08.023

Recommendations

• Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances
• Finding Paths between Graph Colourings: Computational Complexity and Possible Distances
• Finding paths between 3-colourings
• The coloring reconfiguration problem on specific graph classes
• Finding paths between 3-colorings

zbMATH Keywords

PSPACE-completecolour graphsuperpolynomial distancevertex-recolouring

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38)

Cites Work

• Title not available (Why is that?)
• Relationships between nondeterministic and deterministic tape complexities
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Connectedness of the graph of vertex-colourings
• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• Finding paths between 3-colourings
• Mixing 3-Colourings in Bipartite Graphs

Cited In (88)

• The complexity of rerouting shortest paths
• Reconfiguration of vertex covers in a graph
• Reconfiguring vertex colourings of 2-trees
• Reconfiguring graph homomorphisms on the sphere
• Finding Paths between Graph Colourings: Computational Complexity and Possible Distances
• Independent set reconfiguration in cographs and their generalizations
• Recognizing Graphs Close to Bipartite Graphs
• Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters
• Using contracted solution graphs for solving reconfiguration problems
• Connectivity and Hamiltonicity of canonical colouring graphs of bipartite and complete multipartite graphs
• On reconfigurability of target sets
• Recolouring homomorphisms to triangle-free reflexive graphs
• Connected \(k\)-dominating graphs
• Paths between colourings of sparse graphs
• Recolouring reflexive digraphs
• Reconfiguration on nowhere dense graph classes
• Parameterized complexity of optimizing list vertex-coloring through reconfiguration
• A reconfigurations analogue of Brooks' theorem and its consequences
• Reconfiguration of Hamiltonian Cycles in Rectangular Grid Graphs
• Homomorphism reconfiguration via homotopy
• Irredundance graphs
• Parameterized complexity of independent set reconfiguration problems
• Finding shortest paths between graph colourings
• A dichotomy theorem for circular colouring reconfiguration
• Finding shortest paths between graph colourings
• Parameterized complexity of the list coloring reconfiguration problem with graph parameters
• Reconfiguration in bounded bandwidth and tree-depth
• The coloring reconfiguration problem on specific graph classes
• Complexity of independent set reconfigurability problems
• Reconfiguring dominating sets in some well-covered and other classes of graphs
• Introduction to reconfiguration
• Complexity of coloring reconfiguration under recolorability constraints
• The complexity of (list) edge-coloring reconfiguration problem
• On the complexity of reconfiguration problems
• Dominating sets reconfiguration under token sliding
• Shortest paths between shortest paths
• On k-Total Dominating Graphs
• Reconfiguration graphs of shortest paths
• Mixing homomorphisms, recolorings, and extending circular precolorings
• Fast recoloring of sparse graphs
• The \(k\)-dominating graph
• (Lack of) model structures on the category of graphs
• Shortest Paths between Shortest Paths and Independent Sets
• On reconfiguration graphs: an abstraction
• Classification of reconfiguration graphs of shortest path graphs with no induced 4-cycles
• Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances
• Square-free graphs are multiplicative
• A polynomial version of Cereceda's conjecture
• Hard problems that quickly become very easy
• Distributed recoloring
• Reconfiguration of homomorphisms to reflexive digraph cycles
• Approximability of the subset sum reconfiguration problem
• The complexity of dominating set reconfiguration
• Shortest reconfiguration of sliding tokens on subclasses of interval graphs
• Linear-time algorithm for sliding tokens on trees
• Reconfiguration of list edge-colorings in a graph
• Reconfiguration graph for vertex colourings of weakly chordal graphs
• Reconfiguration of list \(L(2,1)\)-labelings in a graph
• Finding paths between 3-colorings
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
• The complexity of dominating set reconfiguration
• An Improved Sufficient Condition for Reconfiguration of List Edge-Colorings in a Tree
• Computational complexity of jumping block puzzles
• Approximability of the Subset Sum Reconfiguration Problem
• On a conjecture of Mohar concerning Kempe equivalence of regular graphs
• Hedetniemi's conjecture and strongly multiplicative graphs
• Algorithms for Coloring Reconfiguration Under Recolorability Constraints
• Digraph redicolouring
• Combinatorial reconfiguration with answer set programming: algorithms, encodings, and empirical analysis
• ZDD-based algorithmic framework for solving shortest reconfiguration problems
• Redicolouring digraphs: directed treewidth and cycle-degeneracy
• On the computational complexity of routing in faulty \(k\)-ary \(n\)-cubes and hypercubes
• Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration
• Optimally reconfiguring list and correspondence colourings
• On dominating graph of graphs, median graphs, partial cubes and complement of minimal dominating sets
• Computational complexity of jumping block puzzles
• Diameter of colorings under Kempe changes
• Reconfiguration of vertex colouring and forbidden induced subgraphs
• Characterizing circular colouring mixing for pq<4 $\frac{p}{q}\lt 4$
• The Hamiltonian path graph is connected for simple \(s,t\) paths in rectangular grid graphs
• Recoloring some hereditary graph classes
• Reconfiguration graph for vertex colourings of weakly chordal graphs
• List recoloring of planar graphs
• The connectivity of Boolean satisfiability: dichotomies for formulas and circuits
• Decremental optimization of vertex-coloring under the reconfiguration framework
• Reconfiguration of maximum-weight \(b\)-matchings in a graph
• Hamiltonian cycle reconfiguration with answer set programming
• Recongo: bounded combinatorial reconfiguration with answer set programming

This page was built for publication: Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances

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