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$.
@article{10_37236_3041,
author = {Peter Allen and Jozef Skokan and Andreas W\"urfl},
title = {Maximum planar subgraphs in dense graphs},
journal = {The electronic journal of combinatorics},
year = {2013},
volume = {20},
number = {3},
doi = {10.37236/3041},
zbl = {1298.05170},
url = {http://geodesic.mathdoc.fr/articles/10.37236/3041/}
}
TY - JOUR
AU - Peter Allen
AU - Jozef Skokan
AU - Andreas Würfl
TI - Maximum planar subgraphs in dense graphs
JO - The electronic journal of combinatorics
PY - 2013
VL - 20
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/3041/
DO - 10.37236/3041
ID - 10_37236_3041
ER -
%0 Journal Article
%A Peter Allen
%A Jozef Skokan
%A Andreas Würfl
%T Maximum planar subgraphs in dense graphs
%J The electronic journal of combinatorics
%D 2013
%V 20
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/3041/
%R 10.37236/3041
%F 10_37236_3041
Peter Allen; Jozef Skokan; Andreas Würfl. Maximum planar subgraphs in dense graphs. The electronic journal of combinatorics, Tome 20 (2013) no. 3. doi: 10.37236/3041
