Filling the Complexity Gaps for Colouring Planar and Bounded Degree Graphs

A colouring of a graph $G=(V,E)$ is a function $c: V\rightarrow{1,2,\ldots }$suchthat$c(u)\neq c(v)$forevery$uv\in E$\mathrm{.}A$k$-regular list assignment of $G$ is a function $L$ with domain $V$ such that for every $u\in V$,$L(u)$isasubsetof${1, 2, \dots}$ofsize$k$\mathrm{.}Acolouring$c$of$G$respectsa$k$-regularlistassignment$L$of$G$if$c(u)\in L(u)$forevery$u\in V$\mathrm{.}Agraph$G$is$k$-choosableifforevery$k$-regularlistassignment$L$of$G$,thereexistsacolouringof$G$thatrespects$L$. We may also ask if for a given $k$-regular list assignment $L$ of a given graph $G$, there exists a colouring of $G$ that respects $L$. This yields the $k$-Regular List Colouring problem. For $k\in \{3,4\}$ we determine a family of classes ${\cal G}$ofplanargraphs,suchthateither$k$-Regular List Colouring is NP-complete for instances $(G,L)$ with $G\in \mathcal{G}$, or every $G\in {\cal G}$is$k$-choosable\mathrm{.}Byusingknownexamplesofnon-$3$-choosable and non-$4$-choosable graphs, this enables us to classify 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 classify the complexity of $k$-Regular List Colouring and a number of related colouring problems for graphs with bounded maximum degree.