We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Filling the complexity gaps for colouring planar and bounded degree graphs.

Dabrowski, K.K. and Dross, F. and Johnson, M. and Paulusma, D. (2019) 'Filling the complexity gaps for colouring planar and bounded degree graphs.', Journal of graph theory., 92 (4). pp. 377-393.


A colouring of a graphGVE=( ,)is a function→cV:{1, 2,...}such that≠cucv() ()for every∈uvE.Ak‐regular list assignment ofGis a functionLwith domainVsuch that for every∈uV,Lu()is asubset of{1, 2,...}of sizek. A colouringcofGrespects ak‐regular list assignmentLofGif∈cuLu() ()forevery∈uV. A graphGisk‐choosable if for everyk‐regular list assignmentLofG, there exists a colouringofGthat respectsL. We may also ask if for a givenk‐regular list assignmentLof a given graphG, thereexists a colouring ofGthat respectsL. This yields thek‐REGULARLISTCOLOURINGproblem. For∈k{3, 4},wedetermine a family of classeseof planar graphs, suchthat eitherk‐REGULARLISTCOLOURINGisNP‐complete forinstancesGL(,)withe∈G, or everye∈Gisk‐choosable. By using known examples of non‐3‐choosable and non‐4‐choosable graphs, this enables usto classify the complexity ofk‐REGULARLISTCOLOURINGrestricted to planar graphs, planar bipartite graphs,planar triangle‐free graphs, and planar graphs with no4‐cycles and no5‐cycles. We also classify the complexityofk‐REGULARLISTCOLOURINGand a number of relatedcolouring problems for graphs with bounded maximumdegree.

Item Type:Article
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Publisher statement:This is the accepted version of the following article: Dabrowski, K.K., Dross, F., Johnson, M. & Paulusma, D. (2019). Filling the complexity gaps for colouring planar and bounded degree graphs. Journal of Graph Theory 92(4): 377-393., which has been published in final form at This article may be used for non-commercial purposes in accordance With Wiley Terms and Conditions for self-archiving.
Date accepted:14 March 2019
Date deposited:15 March 2019
Date of first online publication:31 May 2019
Date first made open access:31 May 2020

Save or Share this output

Look up in GoogleScholar