Connectedness of the graph of vertex-colourings
From MaRDI portal
Publication:2470462
DOI10.1016/j.disc.2007.07.028zbMath1133.05053OpenAlexW2129794490MaRDI QIDQ2470462
Matthew Johnson, Luis Cereceda, Jan van den Heuvel
Publication date: 14 February 2008
Published in: Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: http://dro.dur.ac.uk/1914/1/1914.pdf
Related Items (65)
Connected \(k\)-dominating graphs ⋮ Paths between colourings of sparse graphs ⋮ Classifying coloring graphs ⋮ On the parameterized complexity of reconfiguration of connected dominating sets ⋮ Ground State Connectivity of Local Hamiltonians ⋮ Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas ⋮ Finding shortest paths between graph colourings ⋮ Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas ⋮ In most 6-regular toroidal graphs all 5-colorings are Kempe equivalent ⋮ Parameterized complexity of reconfiguration of atoms ⋮ Mixing Homomorphisms, Recolorings, and Extending Circular Precolorings ⋮ Reconfiguration of dominating sets ⋮ Reconfiguration on nowhere dense graph classes ⋮ Reconfiguring dominating sets in some well-covered and other classes of graphs ⋮ Reconfiguration graphs of shortest paths ⋮ Mixing colourings in \(2K_2\)-free graphs ⋮ Rerouting shortest paths in planar graphs ⋮ Vertex Cover Reconfiguration and Beyond ⋮ Unnamed Item ⋮ Finding Shortest Paths Between Graph Colourings ⋮ The complexity of rerouting shortest paths ⋮ Token sliding on graphs of girth five ⋮ Kempe equivalence of 4‐critical planar graphs ⋮ ZDD-based algorithmic framework for solving shortest reconfiguration problems ⋮ Optimally reconfiguring list and correspondence colourings ⋮ On dominating graph of graphs, median graphs, partial cubes and complement of minimal dominating sets ⋮ Block symmetries in graph coloring reconfiguration systems ⋮ Token sliding on graphs of girth five ⋮ Mixing 3-Colourings in Bipartite Graphs ⋮ Reconfiguration graphs of zero forcing sets ⋮ Fixing improper colorings of graphs ⋮ 5‐Coloring reconfiguration of planar graphs with no short odd cycles ⋮ Reconfiguration of vertex colouring and forbidden induced subgraphs ⋮ Decremental optimization of vertex-coloring under the reconfiguration framework ⋮ Complexity of independent set reconfigurability problems ⋮ Homomorphism complexes, reconfiguration, and homotopy for directed graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Kempe equivalence of colourings of cubic graphs ⋮ On a conjecture of Mohar concerning Kempe equivalence of regular graphs ⋮ Unnamed Item ⋮ Finding paths between 3-colorings ⋮ Cut-colorings in coloring graphs ⋮ Shortest Paths between Shortest Paths and Independent Sets ⋮ On girth and the parameterized complexity of token sliding and Token Jumping ⋮ The \(k\)-dominating graph ⋮ Shortest paths between shortest paths ⋮ Classification of reconfiguration graphs of shortest path graphs with no induced 4-cycles ⋮ On k-Total Dominating Graphs ⋮ Reconfiguration of homomorphisms to reflexive digraph cycles ⋮ Dominating sets reconfiguration under token sliding ⋮ Reconfiguration graph for vertex colourings of weakly chordal graphs ⋮ Kempe equivalence of colourings of cubic graphs ⋮ Reconfiguring vertex colourings of 2-trees ⋮ Independent Set Reconfiguration in Cographs and their Generalizations ⋮ Recolouring weakly chordal graphs and the complement of triangle-free graphs ⋮ A Reconfigurations Analogue of Brooks' Theorem and Its Consequences ⋮ Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances ⋮ Reconfiguration graphs for dominating sets ⋮ Mixing 3-colourings in bipartite 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
Cites Work
- Torpid mixing of the Wang-Swendsen-Kotecký algorithm for sampling colorings
- Improved bounds for sampling colorings
- Randomly coloring sparse random graphs with fewer colors than the maximum degree
- A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Connectedness of the graph of vertex-colourings
