The Maximum Size of \(C_4\)-Free Planar Graphs

Abstract

A planar graph is called \(C_4\)-free if it has no cycles of length four. Let \(f(n,C_4)\) denote the maximum size of a \(C_4\)-free planar graph with order \(n\). In this paper, it is shown that \(f(n,C_4) = \left\lfloor \frac{15}{7}(n-2) \right\rfloor – \mu\) for \(n \geq 30\), where \(\mu = 1\) if \(n \equiv 3 \pmod{7}\) or \(n = 32, 33, 37\), and \(\mu = 0\) otherwise.