The t-improper chromatic number of random graphs
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$...
Main Authors: | , |
---|---|
Format: | Journal article |
Language: | English |
Published: |
2008
|