Filling the complexity gaps for colouring planar and bounded degree graphs

A colouring of a graph G = ( V , E ) is a function c : V → { 1 , 2 , … } such that c ( u ) ≠ c ( v ) for every u v ∈ E . A k ‐regular list assignment of G is a function L with domain V such that for every u ∈ V , L ( u ) is a subset of { 1 , 2 , … } of size k . A colouring c of G respects a k ‐regular list assignment L of G if c ( u ) ∈ L ( u ) for every u ∈ V . A graph G is k ‐choosable if for every k ‐regular list assignment L of G , there exists a colouring of G that respects 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 ‐R egular L ist C olouring problem. For k ∈ { 3 , 4 } , we determine a family of classes G of planar graphs, such that either k ‐R egular L ist C olouring is ‐complete for instances ( G , L ) with G ∈ G , or every G ∈ G is k ‐choosable. By using known examples of non‐ 3 ‐choosable and non‐ 4 ‐choosable graphs, this enables us to classify the complexity of k ‐R egular L ist C olouring restricted to planar graphs, planar bipartite graphs, planar triangle‐free graphs, and planar graphs with no 4 ‐cycles and no 5 ‐cycles. We also classify the complexity of k ‐R egular L ist C olouring and a number of related colouring problems for graphs with bounded maximum degree.