Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
From MaRDI portal
Publication:2436666
DOI10.1007/s10878-012-9490-yzbMath1284.05089OpenAlexW2037520741MaRDI QIDQ2436666
Viresh Patel, Ioannis Lignos, Daniël Paulusma, Matthew Johnson, Marthe Bonamy
Publication date: 25 February 2014
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: http://dro.dur.ac.uk/10709/1/10709.pdf
Related Items (42)
Recoloring Planar Graphs of Girth at Least Five ⋮ Paths between colourings of sparse graphs ⋮ Finding shortest paths between graph colourings ⋮ In most 6-regular toroidal graphs all 5-colorings are Kempe equivalent ⋮ List-recoloring of sparse graphs ⋮ Parameterized complexity of the list coloring reconfiguration problem with graph parameters ⋮ Reconfiguration graphs of shortest paths ⋮ Mixing colourings in \(2K_2\)-free graphs ⋮ On strictly chordality-\(k\) graphs ⋮ Finding Shortest Paths Between Graph Colourings ⋮ Reconfiguration of Vertex Covers in a Graph ⋮ Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration ⋮ Reconfiguration of maximum-weight \(b\)-matchings in a graph ⋮ Parameterized complexity of optimizing list vertex-coloring through reconfiguration ⋮ 5‐Coloring reconfiguration of planar graphs with no short odd cycles ⋮ Strengthening the directed Brooks' theorem for oriented graphs and consequences on digraph redicolouring ⋮ Reconfiguration of vertex colouring and forbidden induced subgraphs ⋮ Decremental optimization of vertex-coloring under the reconfiguration framework ⋮ 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 ⋮ Paths between colourings of graphs with bounded tree-width ⋮ Unnamed Item ⋮ Characterization of 2-path signed network ⋮ An update on reconfiguring 10-colorings of planar graphs ⋮ Linear-time algorithm for sliding tokens on trees ⋮ The complexity of dominating set reconfiguration ⋮ Reconfiguration of list \(L(2,1)\)-labelings in a graph ⋮ Unnamed Item ⋮ Classification of reconfiguration graphs of shortest path graphs with no induced 4-cycles ⋮ Reconfiguration of satisfying assignments and subset sums: easy to find, hard to connect ⋮ A Thomassen-type method for planar graph recoloring ⋮ Reconfiguration graph for vertex colourings of weakly chordal graphs ⋮ Kempe equivalence of colourings of cubic graphs ⋮ Independent Set Reconfiguration in Cographs and their Generalizations ⋮ Algorithms for Coloring Reconfiguration Under Recolorability Constraints ⋮ Recolouring weakly chordal graphs and the complement of triangle-free graphs ⋮ A Reconfigurations Analogue of Brooks' Theorem and Its Consequences ⋮ Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters ⋮ Using contracted solution graphs for solving reconfiguration problems ⋮ Introduction to reconfiguration ⋮ Complexity of Coloring Reconfiguration under Recolorability Constraints
Cites Work
- Unnamed Item
- Unnamed Item
- On the complexity of reconfiguration problems
- On rigid circuit graphs
- Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
- Mixing 3-colourings in bipartite graphs
- Algorithmic graph theory and perfect graphs
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Finding paths between 3-colorings
- Shortest Paths between Shortest Paths and Independent Sets
- Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances
- On the solution‐space geometry of random constraint satisfaction problems
- The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
This page was built for publication: Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
