PLANAR TURAN NUMBER OF THE 6-CYCLE

被引:16
作者
Ghosh, Debarun [1 ]
Gyori, Ervin [1 ,2 ]
Martin, Ryan R. [3 ]
Paulos, Addisu [1 ]
Xiao, Chuanqi
机构
[1] Cent European Univ, Budapest, Hungary
[2] Cent European Univ, Alfred Renyi Inst Math, Budapest, Hungary
[3] Iowa State Univ, Ames, IA 50011 USA
关键词
planar Turan number; extremal planar graph;
D O I
10.1137/21M140657X
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Let ex(P)(n, T, H) denote the maximum number of copies of T in an n-vertex planar graph which does not contain H as a subgraph. When T = K-2, ex(P)(n, T, H) is the well-studied function, the planar Turan number of H, denoted by ex(P)(n, H). The topic of extremal planar graphs was initiated by Dowden [J. Graph Theory, 83 (2016), pp. 213-230]. He obtained a sharp upper bound for both ex(P)(n, C-4) and ex(P)(n, C-5). Later on, Lan, Shi, and Song continued this topic and proved that ex(P)(n, C-6) <= 18(n-2)/7. In this paper, we give a sharp upper bound ex(P)(n, C-6) <= 5/2n - 7, for all n >= 18, which improves Lan, Shi, and Song's result. We also pose a conjecture on ex(P)(n, C-k), for k >= 7.
引用
收藏
页码:2028 / 2050
页数:23
相关论文
共 11 条
[1]  
Cranston DW, 2021, Arxiv, DOI arXiv:2110.02043
[2]   Extremal C4-Free/C5-Free Planar Graphs [J].
Dowden, Chris .
JOURNAL OF GRAPH THEORY, 2016, 83 (03) :213-230
[3]   ON STRUCTURE OF LINEAR GRAPHS [J].
ERDOS, P .
ISRAEL JOURNAL OF MATHEMATICS, 1963, 1 (03) :156-&
[4]  
Erdos P., 1962, Magyar Tud. Akad. Mat. Kutato Int. Kozl, V7, P459
[5]   Planar Turan number of intersecting triangles [J].
Fang, Longfei ;
Wang, Bing ;
Zhai, Mingqing .
DISCRETE MATHEMATICS, 2022, 345 (05)
[6]  
Ghosh D, 2020, Arxiv, DOI arXiv:2006.00994
[7]  
Ghosh D, 2022, Arxiv, DOI arXiv:2110.10515
[8]   Extremal Theta-free planar graphs [J].
Lan, Yongxin ;
Shi, Yongtang ;
Song, Zi-Xia .
DISCRETE MATHEMATICS, 2019, 342 (12)
[9]  
Lan YX, 2019, ELECTRON J COMB, V26
[10]  
Turan Paul, 1941, Matematikai es Fizikai Lapok, V48, P436