Defective and Clustered Colouring of Sparse Graphs

Kevin Hendrey, David R. Wood

Published 2018-06-19Version 1

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 $\frac{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 colouring of graphs with maximum average degree $m$, no $(1-\epsilon)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 $\lfloor \frac{3}{4}m+1\rfloor$-choosable with clustering 2. We then prove a series of results for clustered colouring that explore the trade-off between the number of colours and the clustering. For example, we prove that every graph with maximum average degree $m$ is $\lfloor{\frac{2}{3}m+1}\rfloor$-choosable with clustering $O(m)$. As an example, this implies that every biplanar graph is 8-choosable with bounded clustering. This is the first non-trivial 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.