• search hit 1 of 2
Back to Result List

Large planar subgraphs in dense graphs

Please always quote using this URN:urn:nbn:de:0296-matheon-2835
  • We prove sufficient and essentially necessary conditions in terms of the minimum degree for a graph to contain planar subgraphs with many edges. For example, for all positive γ every sufficiently large graph G with minimum degree at least (2/3 + γ)|G| contains a triangulation as a spanning subgraph, whereas this need not be the case when the minimum degree is less than 2|G|/3.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Daniela Kühn, Deryk Osthus, Anusch Taraz
URN:urn:nbn:de:0296-matheon-2835
Referee:Hans Jürgen Prömel
Document Type:Preprint, Research Center Matheon
Language:English
Date of first Publication:2005/05/11
Release Date:2005/10/31
Institute:Humboldt-Universität zu Berlin
Preprint Number:273
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.