Premium
Filling the complexity gaps for colouring planar and bounded degree graphs
Author(s) -
Dabrowski Konrad K.,
Dross François,
Johnson Matthew,
Paulusma Daniël
Publication year - 2019
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22459
Subject(s) - combinatorics , mathematics , planar graph , bipartite graph , pathwidth , discrete mathematics , bounded function , 1 planar graph , indifference graph , chordal graph , degree (music) , graph , line graph , mathematical analysis , physics , acoustics
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 ‐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.