Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
From MaRDI portal
Publication:2436666
DOI10.1007/S10878-012-9490-YzbMATH Open1284.05089OpenAlexW2037520741MaRDI QIDQ2436666FDOQ2436666
Authors: Marthe Bonamy, Matthew Johnson, Ioannis Lignos, Viresh Patel, Daniël Paulusma 
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
Recommendations
- On the diameter of reconfiguration graphs for vertex colourings
- Reconfiguration graph for vertex colourings of weakly chordal graphs
- Recolouring weakly chordal graphs and the complement of triangle-free graphs
- Paths between colourings of sparse graphs
- Reconfiguring colorings of graphs with bounded maximum average degree
Cites Work
- Algorithmic graph theory and perfect graphs
- Title not available (Why is that?)
- On rigid circuit graphs
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Mixing 3-colourings in bipartite graphs
- Finding paths between 3-colorings
- Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
- The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
- On the complexity of reconfiguration problems
- On the solution-space geometry of random constraint satisfaction problems
- Title not available (Why is that?)
- Shortest Paths between Shortest Paths and Independent Sets
- Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances
Cited In (46)
- Reconfiguration of vertex covers in a graph
- Independent set reconfiguration in cographs and their generalizations
- Paths between colourings of graphs with bounded tree-width
- Kempe equivalence of colourings of cubic graphs
- Algorithms for Coloring Reconfiguration Under Recolorability Constraints
- Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters
- Using contracted solution graphs for solving reconfiguration problems
- Characterization of 2-path signed network
- Redicolouring digraphs: directed treewidth and cycle-degeneracy
- Paths between colourings of sparse graphs
- Parameterized complexity of optimizing list vertex-coloring through reconfiguration
- A reconfigurations analogue of Brooks' theorem and its consequences
- Finding shortest paths between graph colourings
- Finding shortest paths between graph colourings
- Parameterized complexity of the list coloring reconfiguration problem with graph parameters
- On strictly chordality-\(k\) graphs
- In most 6-regular toroidal graphs all 5-colorings are Kempe equivalent
- Recognizing graphs close to bipartite graphs with an application to colouring reconfiguration
- Introduction to reconfiguration
- Complexity of coloring reconfiguration under recolorability constraints
- The complexity of (list) edge-coloring reconfiguration problem
- List-recoloring of sparse graphs
- A Thomassen-type method for planar graph recoloring
- Recoloring Planar Graphs of Girth at Least Five
- An update on reconfiguring 10-colorings of planar graphs
- Reconfiguration graphs of shortest paths
- 5‐Coloring reconfiguration of planar graphs with no short odd cycles
- On reconfiguration graphs: an abstraction
- Classification of reconfiguration graphs of shortest path graphs with no induced 4-cycles
- Strengthening the directed Brooks' theorem for oriented graphs and consequences on digraph redicolouring
- Reconfiguration of vertex colouring and forbidden induced subgraphs
- Title not available (Why is that?)
- The Hamiltonian path graph is connected for simple \(s,t\) paths in rectangular grid graphs
- Recoloring some hereditary graph classes
- Recolouring weakly chordal graphs and the complement of triangle-free graphs
- Reconfiguration graph for vertex colourings of weakly chordal graphs
- Linear-time algorithm for sliding tokens on trees
- Mixing colourings in \(2K_2\)-free graphs
- Kempe equivalence of colourings of cubic graphs
- List recoloring of planar graphs
- Reconfiguration graph for vertex colourings of weakly chordal graphs
- Reconfiguration of list \(L(2,1)\)-labelings in a graph
- Decremental optimization of vertex-coloring under the reconfiguration framework
- Reconfiguration of maximum-weight \(b\)-matchings in a graph
- The complexity of dominating set reconfiguration
- On a conjecture of Mohar concerning Kempe equivalence of regular graphs
This page was built for publication: Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2436666)
