Planar Graphs have Independence Ratio at least 3/13

Abstract

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$. In 1968, Erdős asked whether this bound on independence number could be proved more easily than the full 4CT. In 1976 Albertson 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}$.

25 pages, 9 figures