Improper colouring of (random) unit disk graphs

Ross J. Kang 1 Tobias Müller 1 Jean-Sébastien Sereni 2
2 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
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).
Type de document :
Communication dans un congrès
Stefan Felsner. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), pp.193-198, 2005, DMTCS Proceedings
Liste complète des métadonnées


https://hal.inria.fr/hal-01184358
Contributeur : Coordination Episciences Iam <>
Soumis le : vendredi 14 août 2015 - 11:37:16
Dernière modification le : jeudi 11 mai 2017 - 01:09:12
Document(s) archivé(s) le : dimanche 15 novembre 2015 - 10:59:47

Fichier

dmAE0138.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01184358, version 1

Collections

Citation

Ross J. Kang, Tobias Müller, Jean-Sébastien Sereni. Improper colouring of (random) unit disk graphs. Stefan Felsner. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), pp.193-198, 2005, DMTCS Proceedings. <hal-01184358>

Partager

Métriques

Consultations de
la notice

264

Téléchargements du document

37