An H-free graph is a graph not containing the given graph H as a subgraph. It is well known that the Turán number $ \mathrm{{ex}}_{}(n,H) $ is the maximum number of edges in an H-free graph on n vertices. Based on this definition, we define $ \mathrm{{ex}}_{_\mathcal {P}}(n,H) $ to restrict the graph classes to planar graphs, that is, $ \mathrm{{ex}}_{_\mathcal {P}}(n,H)=\max \{|E(G)|: G\in {\mathcal {G}} $, where $ {\mathcal {G}} $ is a family of all H-free planar graphs on n vertices. Obviously, we have $ \mathrm{{ex}}_{_{\mathcal {P}}}(n,H)=3n-6 $ if the graph H is not a planar graph. The study is initiated by Dowden (J Graph Theory 83:213–230, 2016), who obtained some results when H is considered as $ C_4 $ or $ C_5 $. In this paper, we determine the values of $ \mathrm{{ex}}_{_{\mathcal {P}}}(n,P_k) $ with $ k\in \{8,9\} $, where $ P_k $ is a path with k vertices.
Yong-Xin Lan, Yong-Tang Shi
. Extremal P8-Free/P9-Free Planar Graphs[J]. Journal of the Operations Research Society of China, 2023
, 11(3)
: 451
-457
.
DOI: 10.1007/s40305-021-00385-2
[1] Gu, R., Li, J., Shi, Y.: Anti-Ramsey numbers of paths and cycles in hypergraphs. SIAM J. Discrete Math. 34(1), 271–307(2020)
[2] Kostochka, A., Mubayi, D., Verstraëte, J.: Turán problems and shadows II: trees. J. Combin. Theory Ser. B 122, 457–478(2017)
[3] Füredi, Z.: Turán type problems, “Surveys in Combinatorics”. Lond. Math. Soc. Lect. Note Ser. 166, 253–300(1991)
[4] Lan, Y., Shi, Y., Song, Z.: Planar Turán number and planar anti-Ramsey number of graphs. Oper. Res. Trans. 25(3), 200–216(2021)
[5] Yuan, L., Zhang, X.: The Turán number of disjoint copies of paths. Discrete Math. 340, 132–139(2017)
[6] Dowden, C.: Extremal C4-free/C5-free planar graphs. J. Graph Theory 83, 213–230(2016)
[7] Lan, Y., Shi, Y., Song, Z.: Extremal Theta-free planar graphs. Discrete Math. 342, 111610(2019)
[8] Lan, Y., Shi, Y., Song, Z.: Extremal H-free planar graphs. Electron. J. Combin. 26(2), P2.11(2019)
[9] Lan, Y., Shi, Y.: Planar Turán numbers of short paths. Graphs Combin. 35, 1035–1049(2019)
