The t-stability number of a random graph

Journal article

Given a graph G = (V,E), a vertex subset S is called t-stable (or t-dependent) if the subgraph G[S] induced on S has maximum degree at most t. The t-stability number of G is the maximum order of a t-stable set in G. We investigate the typical values that this parameter takes on a random graph on n vertices and edge probability equal to p. For any fixed 0 < p < 1 and fixed non-negative integer t, we show that, with probability tending to 1 as n grows, the t-stability number takes on at most two values which we identify as functions of t, p and n. The main tool we use is an asymptotic expression for the expected number of t-stable sets of order k. We derive this expression by performing a precise count of the number of graphs on k vertices that have maximum degree at most k. Using the above results, we also obtain asymptotic bounds on the t-improper chromatic number of a random graph (this is the generalisation of the chromatic number, where we partition of the vertex set of the graph into t-stable sets).

Authors: Fountoulakis, N; Kang, R; McDiarmid, C

• Publication status: Published
• Journal: Electron. J. Combin. 17 (2010), #R59
• Volume: 17
• Issue: 1
• Pages: 1-29
• Publication date: 2008-08-31
• EISSN: 1077-8926
• ISSN: 1077-8926
• Language: English
• Keywords: math.PR; math.CO; 05C80, 05A16