Filling the complexity gaps for colouring planar and bounded degree graphs

Dabrowski, K.K.; Dross, F.; Johnson, M.; Paulusma, D.

Abstract

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.

Citation

Dabrowski, 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. https://doi.org/10.1002/jgt.22459

• Journal Article Type: Article
• Acceptance Date: Mar 14, 2019
• Online Publication Date: May 31, 2019
• Publication Date: Dec 1, 2019
• Deposit Date: Mar 15, 2019
• Publicly Available Date: May 31, 2020
• Journal: Journal of Graph Theory
• Print ISSN: 0364-9024
• Electronic ISSN: 1097-0118
• Publisher: Wiley
• Peer Reviewed: Peer Reviewed
• Volume: 92
• Issue: 4
• Pages: 377-393
• DOI: https://doi.org/10.1002/jgt.22459
• Public URL: https://durham-repository.worktribe.com/output/1335503