Professor Matthew Johnson matthew.johnson2@durham.ac.uk
Head Of Department
Finding Shortest Paths Between Graph Colourings
Johnson, M.; Kratsch, D.; Kratsch, S.; Patel, V.; Paulusma, D.
Authors
D. Kratsch
S. Kratsch
V. Patel
Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor
Abstract
The k-colouring reconguration problem asks whether, for a given graph G, two proper k-colourings and of G, and a positive integer `, there exists a sequence of at most ` + 1 proper k-colourings of G which starts with and ends with and where successive colourings in the sequence dier on exactly one vertex of G. We give a complete picture of the parameterized complexity of the k-colouring reconguration problem for each xed k when parameterized by `. First we show that the k-colouring reconguration problem is polynomial-time solvable for k = 3, settling an open problem of Cereceda, van den Heuvel and Johnson. Then, for all k 4, we show that the k-colouring reconguration problem, when parameterized by `, is xed-parameter tractable (addressing a question of Mouawad, Nishimura, Raman, Simjour and Suzuki) but that it has no polynomial kernel unless the polynomial hierarchy collapses.
Journal Article Type | Article |
---|---|
Acceptance Date | Apr 30, 2015 |
Online Publication Date | May 12, 2015 |
Publication Date | Jun 1, 2016 |
Deposit Date | May 25, 2015 |
Publicly Available Date | May 12, 2016 |
Journal | Algorithmica |
Print ISSN | 0178-4617 |
Electronic ISSN | 1432-0541 |
Publisher | Springer |
Peer Reviewed | Peer Reviewed |
Volume | 75 |
Issue | 2 |
Pages | 295-321 |
DOI | https://doi.org/10.1007/s00453-015-0009-7 |
Keywords | Graph colouring, Graph algorithms, Reconfigurations, Reconfiguration graphs, Fixed parameter tractability. |
Public URL | https://durham-repository.worktribe.com/output/1407581 |
Files
Accepted Journal Article
(460 Kb)
PDF
Copyright Statement
The final publication is available at Springer via http://dx.doi.org/10.1007/s00453-015-0009-7
You might also like
Computing weighted subset transversals in H-free graphs
(2021)
Presentation / Conference Contribution
Computing subset transversals in H-free graphs
(2020)
Presentation / Conference Contribution
Steiner trees for hereditary graph classes
(2020)
Presentation / Conference Contribution
Independent transversals versus transversals
(2019)
Presentation / Conference Contribution
On cycle transversals and their connected variants in the absence of a small linear forest
(2019)
Presentation / Conference Contribution
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search