Maximal planar subgraphs of fixed girth in random graphs
type: Item
instance of: scholarly article
title: Maximal planar subgraphs of fixed girth in random graphs
zbMATH Open document ID: 1388.05165
author: Y. Aharonov
published in: The Electronic Journal of Combinatorics
publication date: 2018-06-14T00:00:00Z
full work available at URL: https://arxiv.org/abs/1706.06202
full work available at URL: v25i2p45
review text: Summary: \textit{B. Bollobás} and \textit{A. M. Frieze} [Random Struct. Algorithms 2, No. 1, 225--231 (1991; Zbl 0766.05077)] 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\).
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C60
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 6888454
zbMATH Keywords: planar subgraph
zbMATH Keywords: random graph
zbMATH Keywords: threshold
MaRDI profile type: MaRDI publication profile
arXiv ID: 1706.06202
cites work: Spanning maximal planar subgraphs of random graphs
cites work: Every monotone graph property has a sharp threshold
cites work: Q3656240
cites work: Factors in random graphs
cites work: Embedding Spanning Trees in Random Graphs
Recommended article: Spanning maximal planar subgraphs of random graphs
Recommended article: Maximal biconnected subgraphs of random planar graphs
Recommended article: Q4633852
Recommended article: The maximum degree of random planar graphs
Recommended article: Q5743399
Recommended article: On the Maximum Degree of a Random Planar Graph
Recommended article: Random planar graphs with bounds on the maximum and minimum degrees
Recommended article: On the Non-Planarity of a Random Subgraph
Recommended article: Maximum planar subgraphs in dense graphs
Recommended article: On maximum planar induced subgraphs
description: scientific article