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: | |
| Look up in GoogleScholar |
