Publication details for Professor Matthew JohnsonDabrowski, K.K., Dross, F., Johnson, M. & Paulusma, D. (2016), Filling the complexity gaps for colouring planar and bounded degree graphs, in Lipták, Zsuzsanna & Smyth, William F. eds, Lecture Notes in Computer Science 9538: 26th International Workshop on Combinatorial Algorithms (IWOCA 2015). Verona, Italy, Springer, 100-111.
- Publication type: Conference Paper
- ISSN/ISBN: 9783319295152, 9783319295169
- DOI: 10.1007/978-3-319-29516-9_9
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
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.
Conference date: 5-7 October 2015