The t-Improper Chromatic Number of Random Graphs
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...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
2010
|