Reconfiguration of list edge-colorings in a graph

DOI10.1016/J.DAM.2012.05.014zbMATH Open1252.05064OpenAlexW1970459509MaRDI QIDQ713316FDOQ713316

Authors: Takehiro Ito, Erik D. Demaine, Marcin Kamiński

Publication date: 26 October 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2012.05.014

Recommendations

Reconfiguration of List Edge-Colorings in a Graph
An Improved Sufficient Condition for Reconfiguration of List Edge-Colorings in a Tree
The complexity of (list) edge-coloring reconfiguration problem
The list coloring reconfiguration problem for bounded pathwidth graphs
List-recoloring of sparse graphs

tree graph algorithm planar graph list edge-coloring PSPACE-complete reachability on solution space reconfiguration problem

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

List edge and list total colourings of multigraphs
Relationships between nondeterministic and deterministic tape complexities
PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
25 pretty graph colouring problems
Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
Reconfiguration of List Edge-Colorings in a Graph
Games, puzzles, and computation
The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
On the complexity of reconfiguration problems
Shortest Paths between Shortest Paths and Independent Sets
Finding paths between 3-colourings
Reconfigurations in Graphs and Grids

Cited In (34)

Reconfiguring vertex colourings of 2-trees
Reconfiguration of List Edge-Colorings in a Graph
On girth and the parameterized complexity of token sliding and token jumping
On the parameterized complexity of reconfiguration of connected dominating sets
Using contracted solution graphs for solving reconfiguration problems
Rerouting shortest paths in planar graphs
Shortest reconfiguration paths in the solution space of Boolean formulas
Reconfiguration on nowhere dense graph classes
A reconfigurations analogue of Brooks' theorem and its consequences
Reconfiguration of Hamiltonian Cycles in Rectangular Grid Graphs
Token sliding on graphs of girth five
Irredundance graphs
Kempe equivalent list edge-colorings of planar graphs
Reconfiguring dominating sets in some well-covered and other classes of graphs
Shortest reconfiguration paths in the solution space of Boolean formulas
Introduction to reconfiguration
Token sliding on graphs of girth five
The list coloring reconfiguration problem for bounded pathwidth graphs
The complexity of (list) edge-coloring reconfiguration problem
List-recoloring of sparse graphs
Parameterized complexity of reconfiguration of atoms
Reconfiguration graphs of shortest paths
On reconfiguration graphs: an abstraction
Classification of reconfiguration graphs of shortest path graphs with no induced 4-cycles
Title not available (Why is that?)
Parameterized complexity of reconfiguration of atoms
Approximability of the subset sum reconfiguration problem
Linear-time algorithm for sliding tokens on trees
Reconfiguration of list \(L(2,1)\)-labelings in a graph
Reconfiguration of list \(L(2,1)\)-labelings in a graph
Title not available (Why is that?)
An Improved Sufficient Condition for Reconfiguration of List Edge-Colorings in a Tree
Hamiltonian cycle reconfiguration with answer set programming
Recongo: bounded combinatorial reconfiguration with answer set programming

This page was built for publication: Reconfiguration of list edge-colorings in a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q713316)