\(K_4\)-free subgraphs of random graphs revisited (Q2460631)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | \(K_4\)-free subgraphs of random graphs revisited |
scientific article |
Statements
\(K_4\)-free subgraphs of random graphs revisited (English)
0 references
12 November 2007
0 references
The maximal number of edges in an \(H\)-free subgraph of a random graph \(G(n,p)\) is investigated. Asymptotic results are based on a proof of a conjecture by \textit{Y. Kohayakawa, T. Luczak} and \textit{V. Rödl} [Combinatorica 17, No. 2, 173--213 (1997; Zbl 0889.05068)] on certain regular multi-partite graphs when \(H\) is a complete graph on four vertices.
0 references
random subgraphs
0 references
structural regularity
0 references
cover families of vertices
0 references
neighbourhood functions
0 references
