Filling the complexity gaps for colouring planar and bounded degree graphs

Dabrowski, K. K.; Dross, F.; Johnson, M.; Paulusma, D.

doi:10.1007/978-3-319-29516-9_9

Filling the complexity gaps for colouring planar and bounded degree graphs

Dabrowski, K. K.; Dross, F.; Johnson, M.; Paulusma, D.

Authors

K. K. Dabrowski

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