Planar graphs have independence ratio at least 3/13 (Q311579)

Summary: The 4 color theorem (4CT) implies that every \(n\)-vertex planar graph has an independent set of size at least \(\frac{n}4\); this is best possible, as shown by the disjoint union of many copies of \(K_4\). \textit{P. Erdős} [in: \textit{C. Berge}, Graphes et hypergraphes. Monographies Universitaires de Mathématiques No. 37. Paris: Dunod (1970)] asked whether this bound on independence number could be proved more easily than the full 4CT. \textit{M. O. Albertson} [J. Comb. Theory, Ser. B 20, 84--93 (1976; Zbl 0286.05105)] showed (independently of the 4CT) that every \(n\)-vertex planar graph has an independent set of size at least \(\frac{2n}9\). Until now, this remained the best bound independent of the 4CT. Our main result improves this bound to \(\frac{3n}{13}\).