Finding Paths between Graph Colourings: Computational Complexity and Possible Distances

DOI10.1016/J.ENDM.2007.07.073MaRDI QIDQ3503504zbMATH OpenOpenAlexFDO

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

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

colour graphPSPACE-completenesssuperpolynomial paths

Mathematics Subject Classification ID

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

Recommendations

• Finding shortest paths between graph colourings
• Finding shortest paths between graph colourings
• Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• On finding maximum disjoint paths with different colors: computational complexity and practical LP-based algorithms
• Paths between colourings of sparse graphs
• A note on the complexity of longest path problems related to graph coloring
• On the complexity of path problems in properly colored directed graphs
• Computing and Combinatorics
• Algorithms for finding distance-edge-colorings of graphs

Cites work

• Finding paths between 3-colourings
• Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances
• scientific article; zbMATH DE number 1885142 (Why is no real title available?)
• Mixing 3-Colourings in Bipartite Graphs
• 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
• The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies

Cited in

(16)

• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• On finding maximum disjoint paths with different colors: computational complexity and practical LP-based algorithms
• The complexity of change
• A reconfigurations analogue of Brooks' theorem
• Finding shortest paths between graph colourings
• Finding paths between 3-colorings
• Shortest Paths between Shortest Paths and Independent Sets
• Finding shortest paths between graph colourings
• Finding paths between 3-colourings
• Mixing homomorphisms, recolorings, and extending circular precolorings
• Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances
• Complexity of independent set reconfigurability problems
• scientific article; zbMATH DE number 1390132 (Why is no real title available?)
• Complexity of coloring reconfiguration under recolorability constraints
• Recolouring-resistant colourings
• Shortest paths between shortest paths

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3503504)