Improper colouring of (random) unit disk graphs Original Research Article

For any graph G, the k-improper chromatic number image is the smallest number of colours used in a colouring of G such that each colour class induces a subgraph of maximum degree k. We investigate image for unit disk graphs and random unit disk graphs to generalise results of McDiarmid and Reed [Colouring proximity graphs in the plane, Discrete Math. 199(1–3) (1999) 123–137], McDiarmid [Random channel assignment in the plane, Random Structures Algorithms 22(2) (2003) 187–212], and McDiarmid and Müller [On the chromatic number of random geometric graphs, submitted for publication].