About a Brooks-type theorem for improper colouring

Abstract : A graph is k-improperly -colourable if its vertices can be partitioned into parts such that each part induces a subgraph of maximum degree at most k. A result of Lovasz a states that for any graph G, such a partition exists if l is at least (Δ(G)+1)/(k+1) . When k = 0, this bound can be reduced by Brooks' Theorem, unless G is complete or an odd cycle. We study the following question, which can be seen as a generalisation of the celebrated Brooks' Theorem to improper colouring: does there exist a polynomial-time algorithm that decides whether a graph G of maximum degree Δ has k-improper chromatic number at most (Δ+1)/(k+1) - 1? We show that the answer is no, unless P = N P , when Δ= (k + 1)l, k>0 and l+√l < 2k + 4. We also show that, if G is planar, k = 1 or k = 2, Δ = 2k + 2, and l= 2, then the answer is still no, unless P = N P . These results answer some questions of Cowen et al. [Journal of Graph Theory 24(3):205-219, 1997].
Type de document :
Article dans une revue
The Australasian Journal of Combinatorics, 2009, 43, pp.219--230
Liste complète des métadonnées


https://hal.inria.fr/inria-00223009
Contributeur : Jean-Sébastien Sereni <>
Soumis le : jeudi 8 juillet 2010 - 09:36:41
Dernière modification le : mercredi 14 décembre 2016 - 01:03:29
Document(s) archivé(s) le : jeudi 1 décembre 2016 - 04:15:01

Fichier

CHS09.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00223009, version 4

Collections

Citation

Ricardo Correa, Frédéric Havet, Jean-Sébastien Sereni. About a Brooks-type theorem for improper colouring. The Australasian Journal of Combinatorics, 2009, 43, pp.219--230. <inria-00223009v4>

Partager

Métriques

Consultations de
la notice

278

Téléchargements du document

119