[hal-01184358] Improper colouring of (random) unit disk graphs

For any graph G, the k-\emphimproper 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).

from HAL : Dernières publications http://ift.tt/1J5nzKT