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].
Document type :
Journal articles
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download

Contributor : Jean-Sébastien Sereni <>
Submitted on : Thursday, July 8, 2010 - 9:36:41 AM
Last modification on : Friday, January 4, 2019 - 5:32:57 PM
Long-term archiving on : Thursday, December 1, 2016 - 4:15:01 AM


Files produced by the author(s)


  • HAL Id : inria-00223009, version 4


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⟩



Record views


Files downloads