Skip to Main content Skip to Navigation
Journal articles

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 : Wednesday, June 24, 2020 - 10:48:04 AM
Document(s) archivé(s) le : 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, Combinatorial Mathematics Society of Australasia (Inc.), 2009, 43, pp.219--230. ⟨inria-00223009v4⟩



Record views


Files downloads