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}$.
@article{10_37236_5309,
author = {Daniel W. Cranston and Landon Rabern},
title = {Planar graphs have independence ratio at least 3/13},
journal = {The electronic journal of combinatorics},
year = {2016},
volume = {23},
number = {3},
doi = {10.37236/5309},
zbl = {1344.05051},
url = {http://geodesic.mathdoc.fr/articles/10.37236/5309/}
}
TY - JOUR
AU - Daniel W. Cranston
AU - Landon Rabern
TI - Planar graphs have independence ratio at least 3/13
JO - The electronic journal of combinatorics
PY - 2016
VL - 23
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/5309/
DO - 10.37236/5309
ID - 10_37236_5309
ER -
%0 Journal Article
%A Daniel W. Cranston
%A Landon Rabern
%T Planar graphs have independence ratio at least 3/13
%J The electronic journal of combinatorics
%D 2016
%V 23
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/5309/
%R 10.37236/5309
%F 10_37236_5309
Daniel W. Cranston; Landon Rabern. Planar graphs have independence ratio at least 3/13. The electronic journal of combinatorics, Tome 23 (2016) no. 3. doi: 10.37236/5309
