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.