Filling the complexity gaps for colouring planar and bounded degree graphs. Issue 4 (31st May 2019)

• Record Type: Journal Article
• Authors: Dabrowski, Konrad K.; Dross, François; Johnson, Matthew; Paulusma, Daniël
• Is Part Of: Journal of graph theory. Volume 92:Issue 4(2019)
• Page Start: 377
• Page End: 393
• Publication Date: 2019-05-31
• Subjects: choosability -- list colouring -- maximum degree -- planar graphs; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22459
• Languages: English
• ISSNs: 0364-9024

Abstract

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.