Dabrowski, K.K. and Dross, F. and Johnson, M. and Paulusma, D. (2016) 'Filling the complexity gaps for colouring planar and bounded degree graphs.', in Combinatorial Algorithms : 26th International Workshop, Iwoca 2015, Verona, Italy, October 5-7, 2015, Revised selected papers. New York: Springer, pp. 100-111. Lecture notes in computer science. (9538).
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.
|Item Type:||Book chapter|
|Full text:||(AM) Accepted Manuscript|
Download PDF (270Kb)
|Publisher Web site:||http://dx.doi.org/10.1007/978-3-319-29516-9_9|
|Publisher 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|
|Date accepted:||29 January 2015|
|Date deposited:||11 March 2016|
|Date of first online publication:||20 February 2016|
|Date first made open access:||20 February 2017|
Save or Share this output
|Look up in GoogleScholar|