Improper colouring of (random) unit disk graphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Discrete Mathematics and Theoretical Computer Science Année : 2005

Improper colouring of (random) unit disk graphs

Résumé

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).
Fichier principal
Vignette du fichier
dmAE0138.pdf (156.52 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-01184358 , version 1 (14-08-2015)

Identifiants

Citer

Ross J. Kang, Tobias Müller, Jean-Sébastien Sereni. Improper colouring of (random) unit disk graphs. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.193-198, ⟨10.46298/dmtcs.3402⟩. ⟨hal-01184358⟩
123 Consultations
616 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More