Recoloring graphs via tree decompositions
From MaRDI portal
Publication:1686264
DOI10.1016/j.ejc.2017.10.010zbMath1376.05048arXiv1403.6386OpenAlexW2964077286MaRDI QIDQ1686264
Marthe Bonamy, Nicolas Bousquet
Publication date: 21 December 2017
Published in: European Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1403.6386
Trees (05C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (24)
Recoloring Planar Graphs of Girth at Least Five ⋮ Paths between colourings of sparse graphs ⋮ A polynomial version of Cereceda's conjecture ⋮ Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas ⋮ List-recoloring of sparse graphs ⋮ Reconfiguration on nowhere dense graph classes ⋮ Mixing colourings in \(2K_2\)-free graphs ⋮ Reconfiguring 10-colourings of planar graphs ⋮ Optimally reconfiguring list and correspondence colourings ⋮ Parameterized complexity of optimizing list vertex-coloring through reconfiguration ⋮ Fast recoloring of sparse graphs ⋮ Reconfiguration of vertex colouring and forbidden induced subgraphs ⋮ Decremental optimization of vertex-coloring under the reconfiguration framework ⋮ On a conjecture of Mohar concerning Kempe equivalence of regular graphs ⋮ Paths between colourings of graphs with bounded tree-width ⋮ An update on reconfiguring 10-colorings of planar graphs ⋮ Unnamed Item ⋮ A Thomassen-type method for planar graph recoloring ⋮ Reconfiguration graph for vertex colourings of weakly chordal graphs ⋮ Distributed Recoloring ⋮ Algorithms for Coloring Reconfiguration Under Recolorability Constraints ⋮ Recolouring weakly chordal graphs and the complement of triangle-free graphs ⋮ Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters ⋮ Using contracted solution graphs for solving reconfiguration problems
Cites Work
- Unnamed Item
- Unnamed Item
- On the complexity of reconfiguration problems
- Results on the Grundy chromatic number of graphs
- Fast recoloring of sparse graphs
- Mixing 3-colourings in bipartite graphs
- Some perfect coloring properties of graphs
- Incidence matrices and interval graphs
- A Reconfigurations Analogue of Brooks’ Theorem
- Homomorphism reconfiguration via homotopy
- Finding paths between 3-colorings
- Reconfiguration of List Edge-Colorings in a Graph
- Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances
- Complexity of Finding Embeddings in a k-Tree
- On-line and first fit colorings of graphs
- A Survey of Combinatorial Gray Codes
- A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
This page was built for publication: Recoloring graphs via tree decompositions
