Abstract
We prove that every graph of sufficiently large order n and minimum degree at least 2n/3 contains a triangulation as a spanning subgraph. This is best possible: for all integers n, there are graphs of order n and minimum degree [2n/3] - 1 without a spanning triangulation. (c) 2005 Wiley Periodicals, Inc.
Original language | English |
---|---|
Pages (from-to) | 205-233 |
Number of pages | 29 |
Journal | Journal of Graph Theory |
Volume | 49 |
DOIs | |
Publication status | Published - 1 Jul 2005 |
Keywords
- triangulations
- extremal graph theory
- planar graphs
- regularity lemma