Back to Search
Start Over
Largest subgraph from a hereditary property in a random graph
- Source :
- Discrete Mathematics. 346:113480
- Publication Year :
- 2023
- Publisher :
- Elsevier BV, 2023.
-
Abstract
- We prove that for every non-trivial hereditary family of graphs ${\cal P}$ and for every fixed $p \in (0,1)$, the maximum possible number of edges in a subgraph of the random graph $G(n,p)$ which belongs to ${\cal P}$ is, with high probability, $$ \left(1-\frac{1}{k-1}+o(1)\right)p{n \choose 2}, $$ where $k$ is the minimum chromatic number of a graph that does not belong to ${\cal P}$.
Details
- ISSN :
- 0012365X
- Volume :
- 346
- Database :
- OpenAIRE
- Journal :
- Discrete Mathematics
- Accession number :
- edsair.doi.dedup.....2dfbd7d7326d3b99afeba861836cbee5
- Full Text :
- https://doi.org/10.1016/j.disc.2023.113480