Planar Turán Numbers of Cycles: A Counterexample

Abstract

The planar Turan number ${\text{ex}}_{\mathcal{P}}(C_{\ell },n)$ is the largest number of edges in an $n$-vertex planar graph with no $\ell$-cycle. For $\ell \in \{3,4,5,6\}$, upper bounds on ${\text{ex}}_{\mathcal{P}}(C_{\ell },n)$ are known that hold with equality infinitely often. Ghosh, Györi, Martin, Paulo, and Xiao [arxiv:2004.14094] conjectured an upper bound on ${\text{ex}}_{\mathcal{P}}(C_{\ell },n)$ for every $\ell \ge 7$ and $n$ sufficiently large. We disprove this conjecture for every $\ell \ge 11$. We also propose two revised versions of the conjecture.

arXiv comment9 pages, 2 figures