Abstract
For any graph G, the k-improper chromatic number ¿k(G) 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 ¿k 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].
Original language | English |
---|---|
Pages (from-to) | 1438-1454 |
Journal | Discrete Mathematics |
Volume | 308 |
Issue number | 8 |
DOIs | |
Publication status | Published - 2008 |