Finding paths between 3-colorings
From MaRDI portal
Publication:2998926
DOI10.1002/jgt.20514zbMath1216.05154OpenAlexW2097520314MaRDI QIDQ2998926
Matthew Johnson, Luis Cereceda, Jan van den Heuvel
Publication date: 11 May 2011
Published in: Journal of Graph Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/jgt.20514
Related Items
Connected \(k\)-dominating graphs, Classifying coloring graphs, A polynomial version of Cereceda's conjecture, Ground State Connectivity of Local Hamiltonians, A dichotomy theorem for circular colouring reconfiguration, TS-reconfiguration of dominating sets in circle and circular-arc graphs, Finding shortest paths between graph colourings, Parameterized complexity of the list coloring reconfiguration problem with graph parameters, Mixing Homomorphisms, Recolorings, and Extending Circular Precolorings, Square-free graphs are multiplicative, Reconfiguration of dominating sets, Reconfiguration on nowhere dense graph classes, Reconfiguration graphs of shortest paths, Shortest reconfiguration of sliding tokens on subclasses of interval graphs, Rerouting shortest paths in planar graphs, Congestion-Free Rerouting of Flows on DAGs, The connectivity of Boolean satisfiability: dichotomies for formulas and circuits, Finding Shortest Paths Between Graph Colourings, Degree-Constrained Subgraph Reconfiguration is in P, The complexity of rerouting shortest paths, Reconfiguration in bounded bandwidth and tree-depth, Recoloring graphs via tree decompositions, 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$, Fast recoloring of sparse graphs, Digraph redicolouring, Recolouring homomorphisms to triangle-free reflexive graphs, Fixing improper colorings of graphs, Strengthening the directed Brooks' theorem for oriented graphs and consequences on digraph redicolouring, Decremental optimization of vertex-coloring under the reconfiguration framework, Computational complexity of jumping block puzzles, Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs, The Complexity of (List) Edge-Coloring Reconfiguration Problem, Kempe equivalence of colourings of cubic graphs, On a conjecture of Mohar concerning Kempe equivalence of regular graphs, Unnamed Item, Cut-colorings in coloring graphs, Recoloring graphs of treewidth 2, Linear-time algorithm for sliding tokens on trees, Recolouring reflexive digraphs, Reconfiguring graph homomorphisms on the sphere, Reconfiguration on sparse graphs, The complexity of dominating set reconfiguration, Reconfiguration of list \(L(2,1)\)-labelings in a graph, On the parameterized complexity of reconfiguration problems, Unnamed Item, The \(k\)-dominating graph, Classification of reconfiguration graphs of shortest path graphs with no induced 4-cycles, On k-Total Dominating Graphs, Reconfiguration of satisfying assignments and subset sums: easy to find, hard to connect, Reconfiguration graph for vertex colourings of weakly chordal graphs, Computational complexity of jumping block puzzles, Kempe equivalence of colourings of cubic graphs, Homomorphism Reconfiguration via Homotopy, Diameter of colorings under Kempe changes, Distributed Recoloring, Independent Set Reconfiguration in Cographs and their Generalizations, Algorithms for Coloring Reconfiguration Under Recolorability Constraints, A Reconfigurations Analogue of Brooks' Theorem and Its Consequences, Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters, Hedetniemi's Conjecture and Strongly Multiplicative Graphs, Irredundance 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, On reconfigurability of target sets, Complexity of Coloring Reconfiguration under Recolorability Constraints, ON THE COMPUTATIONAL COMPLEXITY OF ROUTING IN FAULTY K-ARY N-CUBES AND HYPERCUBES
Cites Work
