Filling the Complexity Gaps for Colouring Planar and Bounded Degree Graphs

摘要

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.