Maximum planar subgraphs in dense graphs

Allen, Peter

; and Würfl, Andreas (2013) Maximum planar subgraphs in dense graphs. Electronic Journal of Combinatorics, 20 (3). ISSN 1077-8926

Copy

Küuhn, Osthus and Taraz showed that for each γ >0 there exists C such that any n-vertex graph with minimum degree γn contains a planar subgraph with at least 2n - C edges. We find the optimum value of C for all γ< 1/2 and sufficiently large n

Item Type	Article
Keywords	extremal graph theory,planar graphs
Departments	Mathematics
DOI	P1
Date Deposited	02 Aug 2013 14:01
URI	https://researchonline.lse.ac.uk/id/eprint/51362