An improved upper bound for the planar Turán number of $C_8$
Discrete Mathematics
Summary
The authors study planar graphs, which are networks you can draw without any lines crossing. They focus on graphs that do not contain an 8-cycle, meaning no loop has exactly eight edges. They prove that such graphs have a limited number of edges, specifically at most (69/25) times the number of vertices minus 2, improving previous results. This gives a tighter upper bound on how connected these graphs can be under these conditions.
Authors
Xuqing Bai, Weichan Liu, Xiangxiang Nie, Xin Zhang
Abstract
We prove that every $n$-vertex simple planar graph with no copy of $C_8$ has at most \[ \frac{69}{25}(n-2) \] edges, for every $n\ge 8$. This improves the best known bound \[ \frac{323}{108}n-6 \qquad \text{for every } n\ge 27. \]