## Finding Paths between Graph Colourings: PSPACE-completeness and Superpolynomial Distances

dc.contributor.author | Bonsma, Paul | |

dc.contributor.author | Cereceda, Luis | |

dc.date.accessioned | 2021-12-17T10:07:31Z | |

dc.date.available | 2021-12-17T10:07:31Z | |

dc.date.issued | 2007 | |

dc.description.abstract | Suppose we are given a graph G together with two proper vertex k-colourings of G, α and β. How easily can we decide whether it is possible to transform α into β by recolouring vertices of G one at a time, making sure we always have a proper k-colouring of G? This decision problem is trivial for k=2, and decidable in polynomial time for k=3. Here we prove it is PSPACE-complete for all k >= 4. In particular, we prove that the problem remains PSPACE-complete for bipartite graphs, as well as for: (i) planar graphs and 4 <= k <= 6, and (ii) bipartite planar graphs and k=4. Moreover, the values of k in (i) and (ii) are tight, in the sense that for larger values of k, it is always possible to recolour α to β. We also exhibit, for every k >= 4, a class of graphs {GN,k:N>0}, together with two k-colourings for each GN,k, such that the minimum number of recolouring steps required to transform the first colouring into the second is superpolynomial in the size of the graph: the minimum number of steps is Ω(2N), whereas the size of GN is O(N2). This is in stark contrast to the k=3 case, where it is known that the minimum number of recolouring steps is at most quadratic in the number of vertices. We also show that a class of bipartite graphs can be constructed with this property, and that: (i) for 4 <= k <= 6 planar graphs and (ii) for k=4 bipartite planar graphs can be constructed with this property. This provides a remarkable correspondence between the tractability of the problem and its underlying structure. | en |

dc.identifier.issn | 2197-8085 | |

dc.identifier.uri | https://depositonce.tu-berlin.de/handle/11303/15620 | |

dc.identifier.uri | http://dx.doi.org/10.14279/depositonce-14393 | |

dc.language.iso | en | en |

dc.rights.uri | http://rightsstatements.org/vocab/InC/1.0/ | en |

dc.subject.ddc | 510 Mathematik | en |

dc.subject.other | vertex recolouring | en |

dc.subject.other | colour graph | en |

dc.subject.other | PSPACE-completeness | en |

dc.subject.other | superpolynomial distance | en |

dc.title | Finding Paths between Graph Colourings: PSPACE-completeness and Superpolynomial Distances | en |

dc.type | Research Paper | en |

dc.type.version | submittedVersion | en |

tub.accessrights.dnb | free | en |

tub.affiliation | Fak. 2 Mathematik und Naturwissenschaften>Inst. Mathematik | de |

tub.affiliation.faculty | Fak. 2 Mathematik und Naturwissenschaften | de |

tub.affiliation.institute | Inst. Mathematik | de |

tub.publisher.universityorinstitution | Technische Universität Berlin | en |

tub.series.issuenumber | 2007, 21 | en |

tub.series.name | Preprint-Reihe des Instituts für Mathematik, Technische Universität Berlin | en |

##### Files

##### Original bundle

1 - 1 of 1

Loading…

- Name:
- Report-021-2007.pdf
- Size:
- 206.68 KB
- Format:
- Adobe Portable Document Format
- Description: