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

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.

Mots clés: improper colouring; defective colouring; unit disk graph; interval graph; triangular lattice; hexagonal graph; weigted colouring

Domaines: Mathématique discrète [cs.DM]

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⟩