Large planar subgraphs in dense graphs

Daniela Kuhn; Deryk Osthus; A Taraz

doi:10.1016/j.jctb.2005.04.004

Large planar subgraphs in dense graphs

Daniela Kuhn, Deryk Osthus, A Taraz

Mathematics

Research output: Contribution to journal › Article

19 Citations (Scopus)

Abstract

We prove sufficient and essentially necessary conditions in terms of the minimum degree for a graph Z to contain planar subgraphs with many edges. For example, for all positive gamma every sufficiently large graph G with minimum degree at least (2/3 + gamma) vertical bar G vertical bar contains a triangulation as a sparming subgraph, whereas this need not be the case when the minimum degree is less than 2 vertical bar G vertical bar/3. (c) 2005 Elsevier Inc. All rights reserved..

Original language	English
Pages (from-to)	263-282
Number of pages	20
Journal	Journal of Combinatorial Theory. Series B
Volume	95
DOIs	https://doi.org/10.1016/j.jctb.2005.04.004
Publication status	Published - 1 Nov 2005

Keywords

extremal graph theory
planar subgraphs
regularity lemma

Access to Document

10.1016/j.jctb.2005.04.004

Cite this

@article{e710d25a1bbf47848cd01ce812d1955b,

title = "Large planar subgraphs in dense graphs",

abstract = "We prove sufficient and essentially necessary conditions in terms of the minimum degree for a graph Z to contain planar subgraphs with many edges. For example, for all positive gamma every sufficiently large graph G with minimum degree at least (2/3 + gamma) vertical bar G vertical bar contains a triangulation as a sparming subgraph, whereas this need not be the case when the minimum degree is less than 2 vertical bar G vertical bar/3. (c) 2005 Elsevier Inc. All rights reserved..",

keywords = "extremal graph theory, planar subgraphs, regularity lemma",

author = "Daniela Kuhn and Deryk Osthus and A Taraz",

year = "2005",

month = nov,

day = "1",

doi = "10.1016/j.jctb.2005.04.004",

language = "English",

volume = "95",

pages = "263--282",

journal = "Journal of Combinatorial Theory. Series B",

publisher = "Elsevier",

}

TY - JOUR

T1 - Large planar subgraphs in dense graphs

AU - Kuhn, Daniela

AU - Osthus, Deryk

AU - Taraz, A

PY - 2005/11/1

Y1 - 2005/11/1

N2 - We prove sufficient and essentially necessary conditions in terms of the minimum degree for a graph Z to contain planar subgraphs with many edges. For example, for all positive gamma every sufficiently large graph G with minimum degree at least (2/3 + gamma) vertical bar G vertical bar contains a triangulation as a sparming subgraph, whereas this need not be the case when the minimum degree is less than 2 vertical bar G vertical bar/3. (c) 2005 Elsevier Inc. All rights reserved..

AB - We prove sufficient and essentially necessary conditions in terms of the minimum degree for a graph Z to contain planar subgraphs with many edges. For example, for all positive gamma every sufficiently large graph G with minimum degree at least (2/3 + gamma) vertical bar G vertical bar contains a triangulation as a sparming subgraph, whereas this need not be the case when the minimum degree is less than 2 vertical bar G vertical bar/3. (c) 2005 Elsevier Inc. All rights reserved..

KW - extremal graph theory

KW - planar subgraphs

KW - regularity lemma

UR - http://www.scopus.com/inward/record.url?scp=26944500184&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2005.04.004

DO - 10.1016/j.jctb.2005.04.004

M3 - Article

VL - 95

SP - 263

EP - 282

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

Large planar subgraphs in dense graphs

Abstract

Keywords

Access to Document

Fingerprint

Cite this