Classification of reconfiguration graphs of shortest path graphs with no induced 4-cycles

DOI10.1016/j.disc.2019.111640zbMath1429.05108arXiv1808.09387OpenAlexW2974342837MaRDI QIDQ2279287

John Asplund, Brett M. Werner

Publication date: 12 December 2019

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

Full work available at URL: https://arxiv.org/abs/1808.09387

zbMATH Keywords

reconfiguration graphshortest path graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Distance in graphs (05C12)

Cites Work

• Motion planning with pulley, rope, and baskets
• The complexity of rerouting shortest paths
• On the complexity of reconfiguration problems
• Reconfiguration of list edge-colorings in a graph
• Shortest paths between shortest paths
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Mixing 3-colourings in bipartite graphs
• Reconfiguration graphs of shortest paths
• Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs
• Connectedness of the graph of vertex-colourings
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Finding paths between 3-colorings

This page was built for publication: Classification of reconfiguration graphs of shortest path graphs with no induced 4-cycles