Parameterized complexity of the list coloring reconfiguration problem with graph parameters

DOI10.1016/j.tcs.2018.05.005zbMath1395.68153OpenAlexW2963170745MaRDI QIDQ1643161

Xiao Zhou, Takehiro Ito, Tatsuhiko Hatanaka

Publication date: 18 June 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/8106/

zbMATH Keywords

graph algorithmlist coloringfixed-parameter algorithmW[1-hardness]combinatorial reconfiguration

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Fixed-parameter algorithms for graph constraint logic ⋮ Parameterized complexity of optimizing list vertex-coloring through reconfiguration ⋮ Unnamed Item ⋮ Dismantlability, Connectedness, and Mixing in Relational Structures ⋮ Algorithms for Coloring Reconfiguration Under Recolorability Constraints ⋮ Using contracted solution graphs for solving reconfiguration problems

Cites Work

• Unnamed Item
• A dichotomy theorem for circular colouring reconfiguration
• Finding shortest paths between graph colourings
• A survey of the algorithmic aspects of modular decomposition
• On the complexity of reconfiguration problems
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Reconfiguration in bounded bandwidth and tree-depth
• The coloring reconfiguration problem on specific graph classes
• Linear-time modular decomposition of directed graphs
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
• Parameterized Algorithms for Modular-Width
• The complexity of change
• The List Coloring Reconfiguration Problem for Bounded Pathwidth Graphs
• The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration
• Homomorphism reconfiguration via homotopy
• Finding paths between 3-colorings
• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances
• Implicat Representation of Graphs
• Transitiv orientierbare Graphen

This page was built for publication: Parameterized complexity of the list coloring reconfiguration problem with graph parameters