Filling the complexity gaps for colouring planar and bounded degree graphs. Issue 4 (31st May 2019) - Dabrowski, Konrad K.
Abstract: 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 ‐Regular List Colouring problem. For k ∈ { 3, 4 }, we determine a family of classes G of planar graphs, such that either k ‐Regular List Colouring 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 ‐Regular List Colouring 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 ‐Regular List Colouring and a number of related colouring problems for graphs with bounded maximum degree.