We consider a natural generalisation of the independence and chromatic 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 ehaviour 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.