Journal article

### The t-improper chromatic number of random graphs

Abstract:
We consider the $t$-improper chromatic number of the Erd{\H o}s-R{\'e}nyi random graph $G(n,p)$. The t-improper chromatic number $\chi^t(G)$ of $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 $\chi^t(G(n,p))$ over the range of choices for the growth of $t = t(n)$.

### Access Document

Publisher copy:
10.1017/S0963548309990216

### Authors

Journal:
Combin. Probab. Comput. 19 (2010), 87-98
Volume:
19
Issue:
SPEC. ISS.
Pages:
87-98
Publication date:
2008-09-26
DOI:
EISSN:
1571-0653
ISSN:
1571-0653
URN:
uuid:4837fb8d-c30a-4a88-96a0-fb2993fee6a8
Source identifiers:
97474
Local pid:
pubs:97474
Language:
English
Keywords: