Back to Search Start Over

Maximum chordal subgraphs of random graphs

Authors :
Krivelevich, Michael
Zhukovskii, Maksim
Publication Year :
2023

Abstract

We find asymptotics of the maximum size of a chordal subgraph in a binomial random graph $G(n,p)$, for $p=\mathrm{const}$ and $p=n^{-\alpha+o(1)}$.

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2308.08944
Document Type :
Working Paper
Full Text :
https://doi.org/10.1017/S0963548324000154