Maximum Planar Subgraphs in Dense Graphs

Peter Allen, Jozef Skokan, Andreas Würfl

Abstract


Kühn, 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$.

Keywords


Extremal graph theory; Planar graphs

Full Text: PDF