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 (69)
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
This page was built for publication: Finding paths between 3-colorings
