%0 Journal Article
%T Filling the Complexity Gaps for Colouring Planar and Bounded Degree Graphs
%A Konrad K. Dabrowski
%A Francois Dross
%A Matthew Johnson
%A Daniel Paulusma
%J Computer Science
%D 2015
%I arXiv
%X 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.
%U http://arxiv.org/abs/1506.06564v3