Extremal C4-free/C5-free planar graphs

Abstract

We study the topic of "extremal" planar graphs, defining $\mathrm{e}{\mathrm{x}}_{{}_{\mathcal{P}}}(n,H)$ to be the maximum number of edges possible in a planar graph on $n$ vertices that does not contain a given graph $H$ as a subgraph. In particular,we examine the case when $H$ is a small cycle,obtaining $\mathrm{e}{\mathrm{x}}_{{}_{\mathcal{P}}}(n,C_4)\le \frac{15}{7}(n-2)$ for all $n\ge 4$ and $\mathrm{e}{\mathrm{x}}_{{}_{\mathcal{P}}}(n,C_5)\le \frac{12n-33}{5}$ for all $n\ge 11$, and showing that both of these bounds are tight.

20 pages