Parameterized complexity of the list coloring reconfiguration problem with graph parameters
type: Item
instance of: scholarly article
title: Parameterized complexity of the list coloring reconfiguration problem with graph parameters
zbMATH Open document ID: 1395.68153
author: Tatsuhiko Hatanaka
author: Takehiro Ito
author: Xiao Zhou
published in: Theoretical Computer Science
publication date: 2018-06-18T00:00:00Z
full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/8106/
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 6890643
zbMATH Keywords: combinatorial reconfiguration
zbMATH Keywords: graph algorithm
zbMATH Keywords: list coloring
zbMATH Keywords: fixed-parameter algorithm
zbMATH Keywords: W[1]-hardness
MaRDI profile type: Publication
OpenAlex ID: W2963170745
cites work: Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
cites work: Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
cites work: The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration
cites work: A dichotomy theorem for circular colouring reconfiguration
cites work: Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances
cites work: Finding paths between 3-colorings
cites work: Q4503944
cites work: Randomly coloring sparse random graphs with fewer colors than the maximum degree
cites work: Parameterized Algorithms for Modular-Width
cites work: Transitiv orientierbare Graphen
cites work: A survey of the algorithmic aspects of modular decomposition
cites work: The List Coloring Reconfiguration Problem for Bounded Pathwidth Graphs
cites work: The coloring reconfiguration problem on specific graph classes
cites work: On the complexity of reconfiguration problems
cites work: Finding shortest paths between graph colourings
cites work: Implicat Representation of Graphs
cites work: Linear-time modular decomposition of directed graphs
cites work: The complexity of change
cites work: Homomorphism reconfiguration via homotopy
cites work: Reconfiguration in bounded bandwidth and tree-depth
Wikidata QID: Q129860106
DOI: 10.1016/J.TCS.2018.05.005
Recommended article: Parameterized Complexity of the List Coloring Reconfiguration Problem with Graph Parameters
Recommended article: Parameterized complexity of optimizing list vertex-coloring through reconfiguration
Recommended article: Parameterized complexity of list coloring and max coloring
Recommended article: The Complexity of (List) Edge-Coloring Reconfiguration Problem
Recommended article: The List Coloring Reconfiguration Problem for Bounded Pathwidth Graphs
Recommended article: Some (in)tractable parameterizations of coloring and list-coloring
Recommended article: Q5874290
Recommended article: Parameterized Pre-Coloring Extension and List Coloring Problems
Recommended article: Parameterized complexity of conflict-free graph coloring
Recommended article: Parameterized Complexity of Conflict-Free Graph Coloring
description: scientific article; zbMATH DE number 6890643