Maximum planar subgraphs in dense graphs

MaRDI QIDQ396794zbMATH OpenFDO

Authors Peter Allen, J. Skokan, Andreas Würfl

Publication date 14 August 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1301.1604, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i3p1

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

extremal graph theoryplanar graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Extremal problems in graph theory (05C35) Density (toughness, etc.) (05C42)

Abstract: K"uhn, Osthus and Taraz 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.

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\).

Recommendations

• Large planar subgraphs in dense graphs
• Subgraphs with restricted degrees of their vertices in planar graphs
• Concentration of maximum degree in random planar graphs
• On Graphs Which Contain All Sparse Graphs
• On the frequency of 3-connected subgraphs of planar graphs

Cites work

• An extension of the blow-up lemma to arrangeable graphs
• Blow-up lemma
• Graphs with linearly bounded Ramsey numbers
• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• scientific article; zbMATH DE number 878896 (Why is no real title available?)
• Large planar subgraphs in dense graphs
• On the structure of linear graphs
• Radius two trees specify χ‐bounded classes
• Some new results in extremal graph theory
• Spanning triangulations in graphs

Cited in

(7)

• Maximal planar subgraphs of fixed girth in random graphs
• Properties of \(\pi\)-skew graphs with applications
• Large planar subgraphs in dense graphs
• On the frequency of 3-connected subgraphs of planar graphs
• On Graphs Which Contain All Sparse Graphs
• An extension of the blow-up lemma to arrangeable graphs
• AN ELEMENTARY SET FOR EMBEDDED BOUQUET GRAPHS WITH TWO CYCLES

This page was built for publication: Maximum planar subgraphs in dense graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q396794)