Maximal Planar Subgraphs of Fixed Girth in Random Graphs
classification
🧮 math.CO
keywords
maximalplanarcontainsubgraphfixedgirththresholdbipartite
read the original abstract
In 1991, Bollob\'{a}s and Frieze showed that the threshold for $G_{n,p}$ to contain a spanning maximal planar subgraph is very close to $p = n^{-1/3}$. In this paper, we compute similar threshold ranges for $G_{n,p}$ to contain a maximal bipartite planar subgraph and for $G_{n,p}$ to contain a maximal planar subgraph of fixed girth $g$.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.