Improper colouring of (random) unit disk graphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2005

Improper colouring of (random) unit disk graphs

Résumé

For any graph $G$, the $k$-improper chromatic number $\chi^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 generalise results where only proper colouring was considered.
Fichier principal
Vignette du fichier
RR-5761.pdf (217.93 Ko) Télécharger le fichier

Dates et versions

inria-00070259 , version 1 (19-05-2006)

Identifiants

  • HAL Id : inria-00070259 , version 1

Citer

Ross J. Kang, Tobias Müller, Jean-Sébastien Sereni. Improper colouring of (random) unit disk graphs. [Research Report] RR-5761, INRIA. 2005, pp.18. ⟨inria-00070259⟩
124 Consultations
183 Téléchargements

Partager

Gmail Facebook X LinkedIn More