Journal of the Operations Research Society of China ›› 2023, Vol. 11 ›› Issue (3): 451-457.doi: 10.1007/s40305-021-00385-2

Previous Articles     Next Articles

Extremal P8-Free/P9-Free Planar Graphs

Yong-Xin Lan1, Yong-Tang Shi2   

  1. 1. School of Science, Hebei University of Technology, Tianjin, 300401, China;
    2. Center for Combinatorics and LPMC, Nankai University, Tianjin, 300071, China
  • Received:2020-02-24 Revised:2021-11-25 Online:2023-09-30 Published:2023-09-07
  • Contact: Yong-Tang Shi, Yong-Xin Lan E-mail:shi@nankai.edu.cn;yxlan0@126.com
  • Supported by:
    Yong-Tang Shi was partially supported by the National Natural Science Foundation of China (Nos. 11922112 and 11771221), the Natural Science Foundation of Tianjin (Nos. 20JCZDJC00840 and 20JCJQJC00090). Yong-Xin Lan was partially supported by the National Natural Science Foundation of China (No. 12001154), the Natural Science Foundation of Hebei Province (No. A2021202025) and the Special Funds for Jointly Building Universities of Tianjin (No. 280000307).

Abstract: 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.

Key words: Turán number, Extremal graph, Planar graph

CLC Number: