Ross Kang, Tobias Müller (1), Jean-Sébastien Sereni (2)
(1) Department of Statistics [Oxford]
(2) Algorithms, simulation, combinatorics and optimization for telecommunications
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 the ratio of the $k$-improper chromatic number to the clique number for unit disk graphs and random unit disk graphs to extend results of [McRe99, McD03] (where they considered only proper colouring).
