- 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)$.
- 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:
- Copyright date:
- 2008
- Notes:
- 12 pages
Journal article
The t-improper chromatic number of random graphs
Actions
Authors
Bibliographic Details
Item Description
Terms of use
Metrics
Altmetrics
Dimensions
If you are the owner of this record, you can report an update to it here: Report update to this record