Planar Turán numbers of cycles: a counterexample

DOI10.37236/10774MaRDI QIDQ2170782zbMATH OpenOpenAlexWikidataFDO

Authors Daniel W. Cranston, Bernard Lidický, Xiaonan Liu, Abhinav Shantanam

Publication date 6 September 2022

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2110.02043

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

extremal planar graphplanar Turán number

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Enumeration in graph theory (05C30) Paths and cycles (05C38)

Abstract: The planar Turan number $extrm{ex}_{mathcalP}(C_{ell},n)$ is the largest number of edges in an $n$-vertex planar graph with no $ell$-cycle. For $ellin3,4,5,6$, upper bounds on $extrm{ex}_{mathcalP}(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 $extrm{ex}_{mathcalP}(C_{ell},n)$ for every $ellge7$ and $n$ sufficiently large. We disprove this conjecture for every $ellge11$. We also propose two revised versions of the conjecture.

Recommendations

• Planar Turán numbers on short cycles of consecutive lengths
• Outerplanar Turán numbers of cycles and paths
• On the Number of Cycles in Planar Graphs
• Cyclomatic numbers of planar graphs
• On the Number of Simple Cycles in Planar Graphs
• scientific article; zbMATH DE number 1107718
• Planar Ramsey numbers for cycles
• Planar anti-Ramsey numbers of paths and cycles
• Planar Turán numbers of short paths
• On the Turán number of some ordered even cycles

Cites work

• scientific article; zbMATH DE number 5174567 (Why is no real title available?)
• Extremal Theta-free planar graphs
• Extremal \(C_{4}\)-free/\(C_{5}\)-free planar graphs
• Extremal \(H\)-free planar graphs
• Long cycles in 3-connected graphs
• Planar Turán number of intersecting triangles
• Proofs from THE BOOK. Including illustrations by Karl H. Hofmann
• Simple paths on polyhedra

Cited in

(8)

• Generalized planar Turán numbers
• Planar Turán number of the disjoint union of cycles
• Planar Turán number of the 6-cycle
• Dense circuit graphs and the planar Turán number of a cycle
• A new construction for the planar Turán number of cycles
• Outerplanar Turán numbers of cycles and paths
• The Turán number of the Fano plane
• Planar Turán numbers of cubic graphs and disjoint union of cycles

This page was built for publication: Planar Turán numbers of cycles: a counterexample

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2170782)