Reconfiguration of list edge-colorings in a graph

DOI10.1016/j.dam.2012.05.014zbMath1252.05064OpenAlexW1970459509MaRDI QIDQ713316

Erik D. Demaine, Takehiro Ito, Marcin Kaminski

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

zbMATH Keywords

treegraph algorithmplanar graphPSPACE-completelist edge-coloringreachability on solution spacereconfiguration problem

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (31)

On the parameterized complexity of reconfiguration of connected dominating sets ⋮ Ground State Connectivity of Local Hamiltonians ⋮ Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas ⋮ Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas ⋮ Parameterized complexity of reconfiguration of atoms ⋮ Reconfiguration of dominating sets ⋮ Reconfiguration on nowhere dense graph classes ⋮ Reconfiguring dominating sets in some well-covered and other classes of graphs ⋮ Reconfiguration graphs of shortest paths ⋮ Rerouting shortest paths in planar graphs ⋮ Token sliding on graphs of girth five ⋮ Reconfiguration of Hamiltonian Cycles in Rectangular Grid Graphs ⋮ Kempe equivalent list edge-colorings of planar graphs ⋮ Token sliding on graphs of girth five ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The Complexity of (List) Edge-Coloring Reconfiguration Problem ⋮ Unnamed Item ⋮ Approximability of the subset sum reconfiguration problem ⋮ On girth and the parameterized complexity of token sliding and Token Jumping ⋮ Linear-time algorithm for sliding tokens on trees ⋮ Reconfiguration on sparse graphs ⋮ Reconfiguration of list \(L(2,1)\)-labelings in a graph ⋮ On the parameterized complexity of reconfiguration problems ⋮ Classification of reconfiguration graphs of shortest path graphs with no induced 4-cycles ⋮ Reconfiguration of satisfying assignments and subset sums: easy to find, hard to connect ⋮ Reconfiguring vertex colourings of 2-trees ⋮ A Reconfigurations Analogue of Brooks' Theorem and Its Consequences ⋮ Irredundance graphs ⋮ Using contracted solution graphs for solving reconfiguration problems ⋮ Introduction to reconfiguration

Cites Work

• Unnamed Item
• Unnamed Item
• On the complexity of reconfiguration problems
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• 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
• Shortest Paths between Shortest Paths and Independent Sets
• Reconfiguration of List Edge-Colorings in a Graph
• Reconfigurations in Graphs and Grids
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• 25 pretty graph colouring problems

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