Skip to Main content Skip to Navigation

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 , Laboratoire I3S - 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.
Document type :
Complete list of metadatas

Cited literature [30 references]  Display  Hide  Download
Contributor : Rapport de Recherche Inria <>
Submitted on : Thursday, May 31, 2007 - 10:14:21 AM
Last modification on : Tuesday, May 26, 2020 - 6:50:22 PM
Long-term archiving on: : Tuesday, September 21, 2010 - 1:18:01 PM


Files produced by the author(s)


  • HAL Id : inria-00150464, version 2


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⟩



Record views


Files downloads