An Improved Sufficient Condition for Reconfiguration of List Edge-Colorings in a Tree

DOI10.1007/978-3-642-20877-5_10zbMath1333.05112OpenAlexW1510285934MaRDI QIDQ3010389

Kazuto Kawamura, Takehiro Ito, Xiao Zhou

Publication date: 1 July 2011

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

Full work available at URL: https://doi.org/10.1007/978-3-642-20877-5_10

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Finding shortest paths between graph colourings, Finding Shortest Paths Between Graph Colourings

Cites Work

• On the complexity of reconfiguration problems
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• List edge and list total colourings of multigraphs
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Reconfiguration of List Edge-Colorings in a Graph
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies