Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters

DOI10.4230/LIPIcs.MFCS.2017.51zbMath1441.68109arXiv1705.07551OpenAlexW2964264940MaRDI QIDQ5111266

Takehiro Ito, Xiao Zhou, Tatsuhiko Hatanaka

Publication date: 26 May 2020

Full work available at URL: https://arxiv.org/abs/1705.07551

zbMATH Keywords

graph algorithmfixed-parameter tractabilitylist coloringW[1-hardness]combinatorial reconfiguration

Mathematics Subject Classification ID

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

Related Items (1)

Introduction to reconfiguration

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
• Recoloring graphs via tree decompositions
• 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
• Implicat Representation of Graphs
• Transitiv orientierbare Graphen

This page was built for publication: Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters