Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
type: Item
instance of: scholarly article
title: Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
zbMATH Open document ID: 1177.05112
author: Paul Bonsma
author: Luis Cereceda
published in: Theoretical Computer Science
publication date: 2009-11-06T00:00:00Z
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 5626889
zbMATH Keywords: vertex-recolouring
zbMATH Keywords: colour graph
zbMATH Keywords: PSPACE-complete
zbMATH Keywords: superpolynomial distance
MaRDI profile type: Publication
full work available at URL: j.tcs.2009.08.023
OpenAlex ID: W2036323482
cites work: Connectedness of the graph of vertex-colourings
cites work: Mixing 3-Colourings in Bipartite Graphs
cites work: Q3104271
cites work: Q5315023
cites work: Randomly coloring sparse random graphs with fewer colors than the maximum degree
cites work: Q4198056
cites work: The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
cites work: PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
cites work: Q4798347
cites work: Q3221403
cites work: Relationships between nondeterministic and deterministic tape complexities
DOI: 10.1016/J.TCS.2009.08.023
description: scientific article; zbMATH DE number 5626889