Back to Search Start Over

Planar Tur\'{a}n Numbers of Cycles: A Counterexample

Authors :
Cranston, Daniel W.
Lidický, Bernard
Liu, Xiaonan
Shantanam, Abhinav
Source :
Electronic Journal of Combinatorics. Vol. 29(3), 2022, #P3.31
Publication Year :
2021

Abstract

The planar Turan 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 $\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\"{o}ri, Martin, Paulo, 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.<br />Comment: 9 pages, 2 figures

Subjects

Subjects :
Mathematics - Combinatorics
05C35

Details

Database :
arXiv
Journal :
Electronic Journal of Combinatorics. Vol. 29(3), 2022, #P3.31
Publication Type :
Report
Accession number :
edsarx.2110.02043
Document Type :
Working Paper