The <i>t</i>-Improper Chromatic Number of Random Graphs

Abstract

We consider the t -improper chromatic number of the Erdős–Rényi random graph G n,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 ( G n,p ) over the range of choices for the growth of t = t ( n ).