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

Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) 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.

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

• scientific article; zbMATH DE number 3641497 (Why is no real title available?)
• scientific article; zbMATH DE number 878896 (Why is no real title available?)
• An extension of the blow-up lemma to arrangeable graphs
• Blow-up lemma
• Graphs with linearly bounded Ramsey numbers
• 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)

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

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)