Finding Paths between Graph Colourings: Computational Complexity and Possible Distances

DOI10.1016/j.endm.2007.07.073zbMath1341.05063OpenAlexW2043294549MaRDI QIDQ3503504

Matthew Johnson, Jan van den Heuvel, Luis Cereceda, Paul Bonsma

Publication date: 5 June 2008

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

Full work available at URL: https://doi.org/10.1016/j.endm.2007.07.073

zbMATH Keywords

PSPACE-completenesscolour graphsuperpolynomial paths

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15)

Related Items (4)

Mixing Homomorphisms, Recolorings, and Extending Circular Precolorings ⋮ Complexity of independent set reconfigurability problems ⋮ Shortest Paths between Shortest Paths and Independent Sets ⋮ Shortest paths between shortest paths

Cites Work

• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Randomly coloring sparse random graphs with fewer colors than the maximum degree
• Mixing 3-Colourings in Bipartite Graphs
• Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
• Unnamed Item
• Unnamed Item

This page was built for publication: Finding Paths between Graph Colourings: Computational Complexity and Possible Distances