Reconfiguration of List Edge-Colorings in a Graph

DOI10.1007/978-3-642-03367-4_33zbMath1253.68263OpenAlexW1509194231MaRDI QIDQ3183470

Erik D. Demaine, Marcin Kaminski, Takehiro Ito

Publication date: 20 October 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/1721.1/73858

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (15)

Connected \(k\)-dominating graphs ⋮ Finding shortest paths between graph colourings ⋮ Finding Shortest Paths Between Graph Colourings ⋮ The complexity of rerouting shortest paths ⋮ Recoloring graphs via tree decompositions ⋮ On dominating graph of graphs, median graphs, partial cubes and complement of minimal dominating sets ⋮ On the complexity of reconfiguration problems ⋮ Complexity of independent set reconfigurability problems ⋮ Shortest Paths between Shortest Paths and Independent Sets ⋮ Approximability of the Subset Sum Reconfiguration Problem ⋮ An Improved Sufficient Condition for Reconfiguration of List Edge-Colorings in a Tree ⋮ The \(k\)-dominating graph ⋮ Reconfiguration of list edge-colorings in a graph ⋮ Shortest paths between shortest paths ⋮ On k-Total Dominating Graphs

Cites Work

• Unnamed Item
• 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
• Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances
• On the Complexity of Reconfiguration Problems
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• Reconfigurations in Graphs and Grids

This page was built for publication: Reconfiguration of List Edge-Colorings in a Graph