 |
Discrete Mathematics & Theoretical Computer Science |
Ross 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.3402Improper colouring of (random) unit disk graphsConference paper
- 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).
Source: HAL:hal-01184358v1
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: [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [en] improper colouring, unit disk graphs, random unit disk graphs, radio channel assignment
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 375 times.
This article's PDF has been downloaded 452 times.