TY - JOUR

T1 - Defective and clustered choosability of sparse graphs

AU - Hendrey, Kevin

AU - Wood, David R.

PY - 2019/9

Y1 - 2019/9

N2 - An (improper) graph colouring has defect d if each monochromatic subgraph has maximum degree at most d, and has clustering c if each monochromatic component has at most c vertices. This paper studies defective and clustered list-colourings for graphs with given maximum average degree. We prove that every graph with maximum average degree less than (2d+2)/(d+2)k is k-choosable with defect d. This improves upon a similar result by Havet and Sereni (J. Graph Theory, 2006). For clustered choosability of graphs with maximum average degree m, no (1-ϵ)m bound on the number of colours was previously known. The above result with d=1 solves this problem. It implies that every graph with maximum average degree m is -choosable with clustering 2. This extends a result of Kopreski and Yu (Discrete Math., 2017) to the setting of choosability. We then prove two results about clustered choosability that explore the trade-off between the number of colours and the clustering. In particular, we prove that every graph with maximum average degree m is -choosable with clustering 9, and is -choosable with clustering O(m). As an example, the later result implies that every biplanar graph is 8-choosable with bounded clustering. This is the best known result for the clustered version of the earth-moon problem. The results extend to the setting where we only consider the maximum average degree of subgraphs with at least some number of vertices. Several applications are presented.

AB - An (improper) graph colouring has defect d if each monochromatic subgraph has maximum degree at most d, and has clustering c if each monochromatic component has at most c vertices. This paper studies defective and clustered list-colourings for graphs with given maximum average degree. We prove that every graph with maximum average degree less than (2d+2)/(d+2)k is k-choosable with defect d. This improves upon a similar result by Havet and Sereni (J. Graph Theory, 2006). For clustered choosability of graphs with maximum average degree m, no (1-ϵ)m bound on the number of colours was previously known. The above result with d=1 solves this problem. It implies that every graph with maximum average degree m is -choosable with clustering 2. This extends a result of Kopreski and Yu (Discrete Math., 2017) to the setting of choosability. We then prove two results about clustered choosability that explore the trade-off between the number of colours and the clustering. In particular, we prove that every graph with maximum average degree m is -choosable with clustering 9, and is -choosable with clustering O(m). As an example, the later result implies that every biplanar graph is 8-choosable with bounded clustering. This is the best known result for the clustered version of the earth-moon problem. The results extend to the setting where we only consider the maximum average degree of subgraphs with at least some number of vertices. Several applications are presented.

KW - 2010 MSC Codes:

KW - Primary 05C15

UR - http://www.scopus.com/inward/record.url?scp=85065253953&partnerID=8YFLogxK

U2 - 10.1017/S0963548319000063

DO - 10.1017/S0963548319000063

M3 - Article

AN - SCOPUS:85065253953

SN - 0963-5483

VL - 28

JO - Combinatorics, Probability and Computing

JF - Combinatorics, Probability and Computing

IS - 5

ER -