Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
From MaRDI portal
(Redirected from Publication:1034528)
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
Cites work
- scientific article; zbMATH DE number 3888913 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1885142 (Why is no real title available?)
- scientific article; zbMATH DE number 2203240 (Why is no real title available?)
- Connectedness of the graph of vertex-colourings
- Finding paths between 3-colourings
- Mixing 3-Colourings in Bipartite Graphs
- PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
- Randomly coloring sparse random graphs with fewer colors than the maximum degree
- Relationships between nondeterministic and deterministic tape complexities
- The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
Cited in
(88)- Approximability of the Subset Sum Reconfiguration Problem
- The complexity of rerouting shortest paths
- Reconfiguring graph homomorphisms on the sphere
- Reconfiguration of vertex covers in a graph
- Hedetniemi's conjecture and strongly multiplicative graphs
- Reconfiguring vertex colourings of 2-trees
- Finding Paths between Graph Colourings: Computational Complexity and Possible Distances
- Independent set reconfiguration in cographs and their generalizations
- Recognizing Graphs Close to Bipartite Graphs
- Using contracted solution graphs for solving reconfiguration problems
- Algorithms for Coloring Reconfiguration Under Recolorability Constraints
- Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters
- Connectivity and Hamiltonicity of canonical colouring graphs of bipartite and complete multipartite graphs
- On reconfigurability of target sets
- Digraph redicolouring
- Combinatorial reconfiguration with answer set programming: algorithms, encodings, and empirical analysis
- Recolouring homomorphisms to triangle-free reflexive graphs
- Connected \(k\)-dominating graphs
- Paths between colourings of sparse graphs
- ZDD-based algorithmic framework for solving shortest reconfiguration problems
- On the computational complexity of routing in faulty \(k\)-ary \(n\)-cubes and hypercubes
- Redicolouring digraphs: directed treewidth and cycle-degeneracy
- 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
- A dichotomy theorem for circular colouring reconfiguration
- Finding shortest paths between graph colourings
- Parameterized complexity of the list coloring reconfiguration problem with graph parameters
- Finding shortest paths between graph colourings
- 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
- Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration
- Optimally reconfiguring list and correspondence colourings
- On the complexity of reconfiguration problems
- The complexity of (list) edge-coloring reconfiguration problem
- Complexity of coloring reconfiguration under recolorability constraints
- Dominating sets reconfiguration under token sliding
- Shortest paths between shortest paths
- On dominating graph of graphs, median graphs, partial cubes and complement of minimal dominating sets
- On k-Total Dominating Graphs
- Reconfiguration graphs of shortest paths
- Computational complexity of jumping block puzzles
- 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
- Diameter of colorings under Kempe changes
- Square-free graphs are multiplicative
- Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances
- Reconfiguration of vertex colouring and forbidden induced subgraphs
- A polynomial version of Cereceda's conjecture
- Hard problems that quickly become very easy
- Characterizing circular colouring mixing for pq<4 $\frac{p}{q}\lt 4$
- Reconfiguration of homomorphisms to reflexive digraph cycles
- The Hamiltonian path graph is connected for simple \(s,t\) paths in rectangular grid graphs
- Approximability of the subset sum reconfiguration problem
- Distributed recoloring
- Linear-time algorithm for sliding tokens on trees
- The complexity of dominating set reconfiguration
- Shortest reconfiguration of sliding tokens on subclasses of interval graphs
- Recoloring some hereditary graph classes
- Reconfiguration of list edge-colorings in a graph
- Reconfiguration graph for vertex colourings of weakly chordal graphs
- Reconfiguration graph for vertex colourings of weakly chordal graphs
- The connectivity of Boolean satisfiability: dichotomies for formulas and circuits
- Reconfiguration of list \(L(2,1)\)-labelings in a graph
- List recoloring of planar graphs
- Finding paths between 3-colorings
- Decremental optimization of vertex-coloring under the reconfiguration framework
- Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
- The complexity of dominating set reconfiguration
- Reconfiguration of maximum-weight b-matchings in a graph
- An Improved Sufficient Condition for Reconfiguration of List Edge-Colorings in a Tree
- Computational complexity of jumping block puzzles
- Hamiltonian cycle reconfiguration with answer set programming
- Recongo: bounded combinatorial reconfiguration with answer set programming
- On a conjecture of Mohar concerning Kempe equivalence of regular graphs
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)
