The t-Improper Chromatic Number of Random Graphs - Kang, R; McDiarmid, C (2010)
We consider the t-improper chromatic number of the Erd′s-Rényi random graph Gn,p. The t-improper chromatic number χt(G) is the smallest number of colours needed in a colouring of the vertices in which each colour class induces a subgraph of maximum degree at most t. If t = 0, then this is the usual notion of proper colouring. When the edge probability p is constant, we provide a detailed description of the asymptotic behaviour of χt(Gn,p) over the range of choices for the growth of t = t(n). © 2009 Cambridge University Press.