Skip to main content

Research Repository

Advanced Search

Filling the complexity gaps for colouring planar and bounded degree graphs

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

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


Authors

K.K. Dabrowski

F. Dross



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

Files

Accepted Journal Article (344 Kb)
PDF

Copyright 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 https://doi.org/10.1002/jgt.22459. This article may be used for non-commercial purposes in accordance With Wiley Terms and Conditions for self-archiving.






You might also like



Downloadable Citations