Planar Turán Numbers of Cycles: A Counterexample

作者：Daniel W. Cranston, Bernard Lidický, Xiaonan Liu, Abhinav Shantanam · 发表于：The Electronic Journal of Combinatorics · 年份：2022 · DOI：10.37236/10774 · 被引用次数：11 · 研究领域：Limits and Structures in Graph Theory、Advanced Graph Theory Research、Markov Chains and Monte Carlo Methods

The planar Turán number $\textrm{ex}_{\mathcal{P}}(C_{\ell},n)$ is the largest number of edges in an $n$-vertex planar graph with no $\ell$-cycle. For each $\ell\in \{3,4,5,6\}$, upper bounds on $\textrm{ex}_{\mathcal{P}}(C_{\ell},n)$ are known that hold with equality infinitely often. Ghosh, Győri, Martin, Paulos, and Xiao [arXiv:2004.14094] conjectured an upper bound on $\textrm{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.