K. K. Dabrowski
Filling the complexity gaps for colouring planar and bounded degree graphs
Dabrowski, K. K.; Dross, F.; Johnson, M.; Paulusma, D.
Authors
F. Dross
Professor Matthew Johnson matthew.johnson2@durham.ac.uk
Head Of Department
Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor
Contributors
Zsuzsanna Lipták
Editor
William F. Smyth
Editor
Abstract
We consider a natural restriction of the List Colouring problem, k-Regular List Colouring, which corresponds to the List Colouring problem where every list has size exactly k. We give a complete classification of the complexity of k-Regular List Colouring restricted to planar graphs, planar bipartite graphs, planar triangle-free graphs and to planar graphs with no 4-cycles and no 5-cycles. We also give a complete classification of the complexity of this problem and a number of related colouring problems for graphs with bounded maximum degree.
Citation
Dabrowski, K. K., Dross, F., Johnson, M., & Paulusma, D. (2016). Filling the complexity gaps for colouring planar and bounded degree graphs. In Z. Lipták, & W. F. Smyth (Eds.), Combinatorial Algorithms : 26th International Workshop, Iwoca 2015, Verona, Italy, October 5-7, 2015, Revised selected papers (100-111). https://doi.org/10.1007/978-3-319-29516-9_9
Conference Name | 26th International Workshop on Combinatorial Algorithms (IWOCA 2015) |
---|---|
Conference Location | Verona, Italy |
Start Date | Oct 5, 2015 |
End Date | Oct 7, 2015 |
Acceptance Date | Jan 29, 2015 |
Online Publication Date | Feb 20, 2016 |
Publication Date | Feb 20, 2016 |
Deposit Date | Aug 12, 2015 |
Publicly Available Date | Feb 20, 2017 |
Pages | 100-111 |
Series Title | Lecture notes in computer science |
Series Number | 9538 |
Series ISSN | 0302-9743 |
Book Title | Combinatorial Algorithms : 26th International Workshop, Iwoca 2015, Verona, Italy, October 5-7, 2015, Revised selected papers. |
ISBN | 9783319295152 |
DOI | https://doi.org/10.1007/978-3-319-29516-9_9 |
Public URL | https://durham-repository.worktribe.com/output/1153098 |
Additional Information | Conference date: 5-7 October 2015 |
Files
Accepted Conference Proceeding
(276 Kb)
PDF
Copyright Statement
The final publication is available at Springer via http://dx.doi.org/http://dx.doi.org/10.1007/978-3-319-29516-9_9
You might also like
Solving Infinite-Domain CSPs Using the Patchwork Property
(2023)
Conference Proceeding
Disjunctive Temporal Problems under Structural Restrictions
(2021)
Conference Proceeding
Fine-Grained Complexity of Temporal Problems
(2020)
Conference Proceeding
Independent transversals versus transversals
(2019)
Conference Proceeding
Filling the complexity gaps for colouring planar and bounded degree graphs
(2019)
Journal Article
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