Extremal H-free planar graphs

被引:0
作者
Lan, Yongxin [1 ,2 ]
Shi, Yongtang [1 ,2 ]
Song, Zi-Xia [3 ]
机构
[1] Nankai Univ, Ctr Combinator, Tianjin, Peoples R China
[2] Nankai Univ, LPMC, Tianjin, Peoples R China
[3] Univ Cent Florida, Dept Math, Orlando, FL 32816 USA
基金
中国国家自然科学基金;
关键词
TURAN NUMBERS;
D O I
暂无
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Given a graph H, a graph is H-free if it does not contain H as a subgraph. We continue to study the topic of "extremal" planar graphs initiated by Dowden [J. Graph Theory 83 (2016) 213 230], that is, how many edges can an H-free planar graph on n vertices have? We define ex(p) (n, H) to be the maximum number of edges in an H-free planar graph on n vertices. We first obtain several sufficient conditions on H which yield ex(p) (n, H) = 3n - 6 for all n >= vertical bar V(H)vertical bar. We discover that the chromatic number of H does not play a role, as in the celebrated Erdos-Stone Theorem. We then completely determine ex(p) (n, H) when H is a wheel or a star. Finally, we examine the case when H is a (t, r)-fan, that is, H is isomorphic to K-1 + tK(r-1), where t >= 2 and r >= 3 are integers. However, determining ex(p)(n, H), when H is a planar subcubic graph, remains wide open.
引用
收藏
页数:17
相关论文
共 15 条
[1]  
Bollobas Bela, 2013, Modern Graph Theory, Graduate texts in mathematics
[2]   Extremal graphs for intersecting cliques [J].
Chen, GT ;
Gould, RJ ;
Pfender, F ;
Wei, B .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2003, 89 (02) :159-171
[3]   Extremal C4-Free/C5-Free Planar Graphs [J].
Dowden, Chris .
JOURNAL OF GRAPH THEORY, 2016, 83 (03) :213-230
[4]   Turan numbers for odd wheels [J].
Dzido, Tomasz ;
Jastrzebski, Andrzej .
DISCRETE MATHEMATICS, 2018, 341 (04) :1150-1154
[5]   A Note on Turan Numbers for Even Wheels [J].
Dzido, Tomasz .
GRAPHS AND COMBINATORICS, 2013, 29 (05) :1305-1309
[6]   EXTREMAL GRAPHS FOR INTERSECTING TRIANGLES [J].
ERDOS, P ;
FUREDI, Z ;
GOULD, RJ ;
GUNDERSON, DS .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1995, 64 (01) :89-100
[7]   ON THE STRUCTURE OF LINEAR GRAPHS [J].
ERDOS, P ;
STONE, AH .
BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 1946, 52 (12) :1087-1091
[8]   EXACT SOLUTION OF THE HYPERGRAPH TURAN PROBLEM FOR K-UNIFORM LINEAR PATHS [J].
Fueredi, Zoltan ;
Jiang, Tao ;
Seiver, Robert .
COMBINATORICA, 2014, 34 (03) :299-322
[9]   Hypergraph Turan numbers of linear cycles [J].
Fueredi, Zoltan ;
Jiang, Tao .
JOURNAL OF COMBINATORIAL THEORY SERIES A, 2014, 123 (01) :252-270
[10]  
Furedi Z., 1991, LONDON MATH SOC LECT, V166, P253, DOI DOI 10.1017/CB09780511666216.010