Filling the complexity gaps for colouring planar and bounded degree graphs

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

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. (2015, October). Filling the complexity gaps for colouring planar and bounded degree graphs. Presented at 26th International Workshop on Combinatorial Algorithms (IWOCA 2015), Verona, Italy

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 26th International Workshop on Combinatorial Algorithms (IWOCA 2015)
• 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
• Print ISSN: 0302-9743
• 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