Reconfiguration of list edge-colorings in a graph
From MaRDI portal
Publication:713316
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
treegraph algorithmplanar graphlist edge-coloringPSPACE-completereachability on solution spacereconfiguration problem
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)