Planar Turán Numbers of Cycles: A Counterexample
Date
2021-10-05
Authors
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
The planar Turan number exP(Cℓ,n) is the largest number of edges in an n-vertex planar graph with no ℓ-cycle. For ℓ∈{3,4,5,6}, upper bounds on exP(Cℓ,n) are known that hold with equality infinitely often. Ghosh, Györi, Martin, Paulo, and Xiao [arXiv:2004.14094] conjectured an upper bound on exP(Cℓ,n) for every ℓ≥7 and n sufficiently large. We disprove this conjecture for every ℓ≥11. We also propose two revised versions of the conjecture.
Series Number
Journal Issue
Is Version Of
Article
Planar Turán Numbers of Cycles: A Counterexample
(The Electronic Journal of Combinatorics,
2022-08-12)
The planar Turán number exP(Cℓ, n) is the largest number of edges in an n-vertex planar graph with no ℓ-cycle. For each ℓ ∈ {3, 4, 5, 6}, upper bounds on exP(Cℓ, n) are known that hold with equality infinitely often. Ghosh, Győri, Martin, Paulos, and Xiao [arXiv:2004.14094] conjectured an upper bound on exP(Cℓ, n) for every ℓ ≥ 7 and n sufficiently large. We disprove this conjecture for every ℓ ≥ 11. We also propose two revised versions of the conjecture.
Versions
Series
Academic or Administrative Unit
Type
Preprint
Comments
This preprint is made available through arXiv:https://arxiv.org/abs/2110.02043.
This work is licensed under the Creative Commons Attribution 4.0 License.