Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances

DOI10.1007/978-3-540-74456-6_65zbMath1147.68529OpenAlexW4237942241MaRDI QIDQ3525616

Luis Cereceda, Paul Bonsma

Publication date: 17 September 2008

Published in: Mathematical Foundations of Computer Science 2007 (Search for Journal in Brave)

Full work available at URL: https://depositonce.tu-berlin.de/handle/11303/15620

zbMATH Keywords

PSPACE-completecolour graphsuperpolynomial distancevertex-recolouring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (16)

Decreasing the maximum average degree by deleting an independent set or a \(d\)-degenerate subgraph ⋮ Parameterized complexity of the list coloring reconfiguration problem with graph parameters ⋮ Reconfiguration of List Edge-Colorings in a Graph ⋮ Reconfiguring 10-colourings of planar graphs ⋮ Recoloring graphs via tree decompositions ⋮ Finding Paths between Graph Colourings: Computational Complexity and Possible Distances ⋮ Digraph redicolouring ⋮ Fixing improper colorings of graphs ⋮ Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs ⋮ An update on reconfiguring 10-colorings of planar graphs ⋮ Recoloring graphs of treewidth 2 ⋮ On the parameterized complexity of reconfiguration problems ⋮ Unnamed Item ⋮ Mixing 3-colourings in bipartite graphs ⋮ Recognizing Graphs Close to Bipartite Graphs ⋮ Introduction to reconfiguration

This page was built for publication: Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances