Maximum planar subgraphs in dense graphs
type: Item
instance of: scholarly article
title: Maximum planar subgraphs in dense graphs
zbMATH Open document ID: 1298.05170
published in: The Electronic Journal of Combinatorics
publication date: 2014-08-14T00:00:00Z
full work available at URL: https://arxiv.org/abs/1301.1604
full work available at URL: v20i3p1
review text: Summary: \textit{D. Kühn} et al. [J. Comb. Theory, Ser. B 95, No. 2, 263--282 (2005; Zbl 1075.05045)] showed that for each \(\gamma>0\) there exists \(C\) such that any \(n\)-vertex graph with minimum degree \(\gamma n\) contains a planar subgraph with at least \(2n-C\) edges. We find the optimum value of \(C\) for all \(\gamma< 1/2\) and sufficiently large \(n\).
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C42
zbMATH DE Number: 6330273
zbMATH Keywords: extremal graph theory
zbMATH Keywords: planar graphs
MaRDI profile type: Publication
arXiv ID: 1301.1604
cites work: An Extension of the Blow-up Lemma to Arrangeable Graphs
cites work: Graphs with linearly bounded Ramsey numbers
cites work: On the structure of linear graphs
cites work: Radius two trees specify χ‐bounded classes
cites work: Blow-up lemma
cites work: Q4878666
cites work: Spanning triangulations in graphs
cites work: Large planar subgraphs in dense graphs
cites work: Some new results in extremal graph theory
cites work: Q4200109
author: Peter Allen
author: J. Skokan
author: Andreas Würfl
description: scientific article; zbMATH DE number 6330273