The t-dependence and t-improper chromatic numbers of random graphs

numbers and study their behaviour in Erdos-Renyi random graphs. The
t-dependence number of a graph G is the size of the largest subset of
the vertices of G whose induced subgraph has maximum degree at most t.
The t-improper chromatic number of G is the smallest number of parts
needed in a partition of the vertex set of G such that each part
induces a subgraph of maximum degree at most t. Clearly, when t = 0,
these parameters are, respectively, the independence and chromatic
numbers of G. For dense random graphs, we determine the asymptotic
behaviour of these parameters over the range of choices for the growth
of t as a function of the number of vertices.

This is joint work with Nikolaos Fountoulakis and Colin McDiarmid.