Finding paths between 3-colorings
From MaRDI portal
Recommendations
- Finding paths between 3-colourings
- Finding Paths between Graph Colourings: Computational Complexity and Possible Distances
- Finding shortest paths between graph colourings
- Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances
- Finding shortest paths between graph colourings
Cites work
Cited in
(83)- Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
- Connected \(k\)-dominating graphs
- Parameterized complexity of the list coloring reconfiguration problem with graph parameters
- Reconfiguration on nowhere dense graph classes
- Reconfiguration graphs of shortest paths
- Reconfiguration in bounded bandwidth and tree-depth
- Recoloring graphs via tree decompositions
- On a conjecture of Mohar concerning Kempe equivalence of regular graphs
- Cut-colorings in coloring graphs
- Recolouring reflexive digraphs
- Reconfiguring graph homomorphisms on the sphere
- The \(k\)-dominating graph
- Irredundance graphs
- On reconfigurability of target sets
- A polynomial version of Cereceda's conjecture
- TS-reconfiguration of dominating sets in circle and circular-arc graphs
- Recoloring graphs of treewidth 2
- Reconfiguration of list \(L(2,1)\)-labelings in a graph
- Classification of reconfiguration graphs of shortest path graphs with no induced 4-cycles
- Reconfiguration graph for vertex colourings of weakly chordal graphs
- Using contracted solution graphs for solving reconfiguration problems
- Connectivity and Hamiltonicity of canonical colouring graphs of bipartite and complete multipartite graphs
- Introduction to reconfiguration
- Rerouting shortest paths in planar graphs
- The connectivity of Boolean satisfiability: dichotomies for formulas and circuits
- Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
- Shortest reconfiguration of sliding tokens on subclasses of interval graphs
- Recolouring homomorphisms to triangle-free reflexive graphs
- Decremental optimization of vertex-coloring under the reconfiguration framework
- Computational complexity of jumping block puzzles
- Independent set reconfiguration in cographs and their generalizations
- A reconfigurations analogue of Brooks' theorem and its consequences
- Classifying coloring graphs
- Finding shortest paths between graph colourings
- Degree-constrained subgraph reconfiguration is in P
- The complexity of (list) edge-coloring reconfiguration problem
- A dichotomy theorem for circular colouring reconfiguration
- Finding shortest paths between graph colourings
- Finding paths between 3-colourings
- On the computational complexity of routing in faulty k-ary n-cubes and hypercubes
- Square-free graphs are multiplicative
- Mixing homomorphisms, recolorings, and extending circular precolorings
- Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances
- The complexity of rerouting shortest paths
- Linear-time algorithm for sliding tokens on trees
- Congestion-free rerouting of flows on DAGs
- On reconfiguration graphs: an abstraction
- Linear transformations between colorings in chordal graphs
- Distributed recoloring
- Algorithms for Coloring Reconfiguration Under Recolorability Constraints
- Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters
- Complexity of coloring reconfiguration under recolorability constraints
- The complexity of dominating set reconfiguration
- Homomorphism reconfiguration via homotopy
- Hedetniemi's conjecture and strongly multiplicative graphs
- On k-Total Dominating Graphs
- Orientations and 3-colourings of graphs.
- Kempe equivalence of colourings of cubic graphs
- Diameter of colorings under Kempe changes
- Kempe equivalence of colourings of cubic graphs
- On dominating graph of graphs, median graphs, partial cubes and complement of minimal dominating sets
- Parameterized complexity of optimizing list vertex-coloring through reconfiguration
- Characterizing circular colouring mixing for pq<4 $\frac{p}{q}\lt 4$
- Computational complexity of jumping block puzzles
- Digraph redicolouring
- Strengthening the directed Brooks' theorem for oriented graphs and consequences on digraph redicolouring
- Hamiltonian cycle reconfiguration with answer set programming
- Recongo: bounded combinatorial reconfiguration with answer set programming
- Combinatorial reconfiguration with answer set programming: algorithms, encodings, and empirical analysis
- Redicolouring digraphs: directed treewidth and cycle-degeneracy
- Reconfiguration graph for vertex colourings of weakly chordal graphs
- On solution discovery via reconfiguration
- Gap preserving reductions between reconfiguration problems
- Reconfiguring homomorphisms to reflexive graphs via a simple reduction
- Optimal PSPACE-hardness of approximating set cover reconfiguration
- Reconfiguration using generalized token jumping
- Strengthening the directed Brooks' theorem for oriented graphs and consequences on digraph redicolouring (extended abstract)
- Some results on vertex separator reconfiguration
- Reconfiguration of digraph homomorphisms
- The tape reconfiguration problem and its consequences for dominating set reconfiguration
- Asymptotically optimal inapproximability of maxmin k-cut reconfiguration
- Coloring reconfiguration under color swapping
- Fast recoloring of sparse graphs
This page was built for publication: Finding paths between 3-colorings
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2998926)
