Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Filling the complexity gaps for colouring planar and bounded degree graphs.

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).

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.

Item Type:Book chapter
Full text:(AM) Accepted Manuscript
Download PDF
(270Kb)
Status:Peer-reviewed
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

Export:
Export
Look up in GoogleScholar