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
Additional Services
| 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 |
