Large planar subgraphs in dense graphs
Large planar subgraphs in dense graphs
复制标题
密集图中的大平面子图
DOI：
10.1016/j.jctb.2005.04.004
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
A. Taraz
中科院分区：
文献类型：
--
作者：
D. Kühn;Deryk Osthus;A. Taraz
本文用最小度的概念证明了一个图包含多边平面子图的充分必要条件。例如，对所有正γ，每个最小度至少为（2/3+γ）的充分大图G| G|包含作为生成子图的三角剖分，而当最小度小于2时，情况不一定如此|G|/3.
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.