Ross J. Kang ; Tobias Müller ; Jean-Sébastien Sereni - Improper colouring of (random) unit disk graphs

dmtcs:3402 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) - https://doi.org/10.46298/dmtcs.3402
Improper colouring of (random) unit disk graphsArticle

Authors: Ross J. Kang ; Tobias Müller 1; Jean-Sébastien Sereni 2

  • 1 Department of Statistics [Oxford]
  • 2 Algorithms, simulation, combinatorics and optimization for telecommunications

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).


Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: improper colouring,unit disk graphs,random unit disk graphs,radio channel assignment,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]
Funding:
    Source : OpenAIRE Graph
  • Funder: Natural Sciences and Engineering Research Council of Canada
  • Large Volume Chemical Probes; Funder: Netherlands Organisation for Scientific Research (NWO); Code: 06902

Consultation statistics

This page has been seen 182 times.
This article's PDF has been downloaded 281 times.