The planar Turán number of $\{K_4,C_5\}$ and $\{K_4,C_6\}$

Abstract

Let $\mathcal{H}$ be a set of graphs. The planar Turán number, $e{x}_{\mathcal{P}}(n,\mathcal{H})$, is the maximum number of edges in an $n$-vertex planar graph which does not contain any member of $\mathcal{H}$ as a subgraph. When $\mathcal{H}=\{H\}$ has only one element, we usually write $e{x}_{\mathcal{P}}(n,H)$ instead. The topic of extremal planar graphs was initiated by Dowden (2016). He obtained sharp upper bound for both $e{x}_{\mathcal{P}}(n,C_5)$ and $e{x}_{\mathcal{P}}(n,K_4)$. Later on, we obtained sharper bound for $e{x}_{\mathcal{P}}(n,\{K_4,C_7\})$. In this paper, we give upper bounds of $e{x}_{\mathcal{P}}(n,\{K_4,C_5\})\le \frac{15}{7}(n-2)$ and $e{x}_{\mathcal{P}}(n,\{K_4,C_6\})\le \frac{7}{3}(n-2)$. We also give constructions which show the bounds are tight for infinitely many graphs.

11 pages, 11 figures. arXiv admin note: text overlap with arXiv:2307.06909