The Library
A dichotomy theorem for circular colouring reconfiguration
Tools
Tools
Tools
Brewster, Richard C., McGuinness, Sean, Moore, Benjamin and Noel, Jonathan A. (2016) A dichotomy theorem for circular colouring reconfiguration. Theoretical Computer Science, 639 . pp. 1-13. doi:10.1016/j.tcs.2016.05.015 ISSN 0304-3975.
|
PDF
WRAP-dichotomy-theorem-circular-colouring-Noel-2016.pdf - Accepted Version - Requires a PDF viewer. Available under License Creative Commons Attribution Non-commercial No Derivatives 4.0. Download (796Kb) | Preview |
Official URL: http://dx.doi.org/10.1016/j.tcs.2016.05.015
Abstract
Let p and q be positive integers with p/q ≥ 2. The “reconfiguration problem” for circular colourings asks, given two (p,q) - colourings f and g of a graph G , is it possible to transform f into g by changing the colour of one vertex at a time such that every intermediate mapping is a (p,q) - colouring? We show that this problem can be solved in polynomial time for 2 ≤ p/q < 4 and that it is PSPACE -complete for p/q ≥ 4. This generalizes a known dichotomy theorem for reconfiguring classical graph colourings. As an application of the reconfiguration algorithm, we show that graphs with fewer than (k − 1)! / 2 cycles of length divisible by k are k -colourable
| Item Type: | Journal Article | ||||||
|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
| Library of Congress Subject Headings (LCSH): | Graph coloring, Homomorphisms (Mathematics) | ||||||
| Journal or Publication Title: | Theoretical Computer Science | ||||||
| Publisher: | Elsevier Science BV | ||||||
| ISSN: | 0304-3975 | ||||||
| Official Date: | 1 August 2016 | ||||||
| Dates: |
|
||||||
| Volume: | 639 | ||||||
| Page Range: | pp. 1-13 | ||||||
| DOI: | 10.1016/j.tcs.2016.05.015 | ||||||
| Status: | Peer Reviewed | ||||||
| Publication Status: | Published | ||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||
| Date of first compliant deposit: | 10 July 2018 | ||||||
| Date of first compliant Open Access: | 10 July 2018 | ||||||
| RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
