Improper colouring of (random) unit disk graphs
Ross J. Kang, Tobias Müller, Jean-Sébastien Sereni
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).
Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page