A New Construction for the Planar Turán Number of Cycles

Győri, Ervin and Varga, Kitti Katalin and Zhu, Xiutao (2024) A New Construction for the Planar Turán Number of Cycles. GRAPHS AND COMBINATORICS, 40 (6). ISSN 0911-0119

Preview	Text s00373-024-02822-4.pdf - Published Version Download (231kB) | Preview
Preview	Text 2304.05584v2.pdf - Published Version Download (86kB) | Preview

Abstract

The planar Turán number exP(n,Ck ) is the maximum number of edges in an n-vertex planar graph not containing a cycle of length k. Let k ≥ 11 and c, d be constants. Cranston et al., and independently Lan and Song showed that exP(n,Ck ) ≥ 3n − 6 − cn/k holds for large n. Moreover, Cranston et al. conjectured that exP(n,Ck ) ≤ 3n −6−dn/klog2 3 when n is large. In this note, we prove that exP(n,Ck ) ≥ 3n −6− 6 · 3log2 3n/klog2 3 holds for every k ≥ 7. This implies that the conjecture of Cranston et al. is essentially best possible.

Actions (login required)

Edit Item