2023/08/17 by Győri, Ervin, Li, Alan, Zhou, Runtian
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2308.09185
Let H be a set of graphs. The planar Turán number, exP(n,H), is the maximum number of edges in an n-vertex planar graph which does not contain any member of H as a subgraph. When H=\H\ has only one element, we usually write exP(n,H) instead. The topic of extremal planar graphs was initiated by Dowden (2016). He obtained sharp upper bound for both exP(n,C5) and exP(n,K4). Later on, we obtained sharper bound for exP(n,\K4,C7\). In this paper, we give upper bounds of exP(n,\K4,C5\)≤ 15\over 7(n-2) and exP(n,\K4,C6\)≤ 7\over 3(n-2). We also give constructions which show the bounds are tight for infinitely many graphs.