The t-stability number of a random graph

zbMATH Open1222.05236arXiv0809.0141MaRDI QIDQ976708FDOQ976708

Authors: Nikolaos Fountoulakis, Ross J. Kang, Colin McDiarmid 

Publication date: 16 June 2010

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: 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).

Full work available at URL: https://arxiv.org/abs/0809.0141

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Asymptotics of the independence number of a random subgraph of the graph \(G(n,r,<s)\)
• Asymptotics of the independence number of a random subgraph of the graph \(G(n, r, < s)\)
• Largest sparse subgraphs of random graphs
• Largest sparse subgraphs of random graphs
• On the stability of some Erdős-Ko-Rado type results

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Vertex degrees (05C07) Asymptotic enumeration (05A16)

Cited In (9)

• How does the chromatic number of a random graph vary?
• On Two Limit Values of the Chromatic Number of a Random Hypergraph
• Maximum weight t-sparse set problem on vector-weighted graphs
• Induced forests and trees in Erdős-Rényi random graph
• Largest sparse subgraphs of random graphs
• Largest sparse subgraphs of random graphs
• Co-2-plex vertex partitions
• Sharp concentration of the equitable chromatic number of dense random graphs
• Non-concentration of the chromatic number of a random graph

This page was built for publication: The \(t\)-stability number of a random graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q976708)