Filling the Complexity Gaps for Colouring Planar and Bounded Degree Graphs

06/22/2015

∙

by   Konrad K. Dabrowski, et al.

∙

0

∙

share

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.