Improper colouring of unit disk graphs

Frédéric Havet 1 Ross Kang 1 Jean-Sébastien Sereni 1
1 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 : Motivated by a satellite communications problem, we consider a generalised colouring problem on unit disk graphs. A colouring is k -improper if no vertex receives the same colour as k +1 of its neighbours. The k -improper chromatic number chi_k (G) is the least number of colours needed in a k -improper colouring of a graph G. The main sub ject of this work is analysing the complexity of computing chi_k for the class of unit disk graph and some related classes, e.g. hexagonal graphs and interval graphs. We show NP-completeness in many restricted cases and also provide both positive and negative approximability results. Due to the challenging nature of this topic, many seemingly simple questions remain: for example, it remains open to determine the complexity of computing k for unit interval graphs.
Type de document :
Rapport
[Research Report] RR-6206, INRIA. 2007, pp.35
Liste complète des métadonnées

Littérature citée [30 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00150464
Contributeur : Rapport de Recherche Inria <>
Soumis le : jeudi 31 mai 2007 - 10:14:21
Dernière modification le : mercredi 31 janvier 2018 - 10:24:04
Document(s) archivé(s) le : mardi 21 septembre 2010 - 13:18:01

Fichiers

RR-6206.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00150464, version 2

Citation

Frédéric Havet, Ross Kang, Jean-Sébastien Sereni. Improper colouring of unit disk graphs. [Research Report] RR-6206, INRIA. 2007, pp.35. 〈inria-00150464v2〉

Partager

Métriques

Consultations de la notice

357

Téléchargements de fichiers

155