The t-improper chromatic number of random graphs

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

2008-09-26

arxiv.org/abs/0809.4726v2

Combin. Probab. Comput. 19 (2010), 87-98

Mathematics

Combinatorics

12 pages

Scientific paper

10.1017/S0963548309990216

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)$.

Affiliated with

Also associated with

No associations

Rating

The t-improper chromatic number of random graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The t-improper chromatic number of random graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The t-improper chromatic number of random graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-653553