Cookies

We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Computer Science

Profile

Publication details for Professor Matthew Johnson

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.

Author(s) from Durham

Abstract

A colouring of a graph urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0001 is a function urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0002 such that urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0003 for every urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0004. A urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0005‐regular list assignment of urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0006 is a function urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0007 with domain urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0008 such that for every urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0009, urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0010 is a subset of urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0011 of size urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0012. A colouring urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0013 of urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0014 respects a urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0015‐regular list assignment urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0016 of urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0017 if urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0018 for every urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0019. A graph urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0020 is urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0021‐choosable if for every urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0022‐regular list assignment urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0023 of urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0024, there exists a colouring of urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0025 that respects urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0026. We may also ask if for a given urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0027‐regular list assignment urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0028 of a given graph urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0029, there exists a colouring of urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0030 that respects urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0031. This yields the urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0032‐Regular List Colouring problem. For urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0033, we determine a family of classes urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0034 of planar graphs, such that either urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0035‐Regular List Colouring is urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0036‐complete for instances urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0037 with urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0038, or every urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0039 is urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0040‐choosable. By using known examples of non‐urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0041‐choosable and non‐urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0042‐choosable graphs, this enables us to classify the complexity of urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0043‐Regular List Colouring restricted to planar graphs, planar bipartite graphs, planar triangle‐free graphs, and planar graphs with no urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0044‐cycles and no urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0045‐cycles. We also classify the complexity of urn:x-wiley:03649024:media:jgt22459:jgt22459-math-0046‐Regular List Colouring and a number of related colouring problems for graphs with bounded maximum degree.