Back to Search
Start Over
Planar Graphs have Independence Ratio at least 3/13
- Source :
- Electronic Journal of Combinatorics. Vol. 23(3), 2016, #P3.45
- Publication Year :
- 2016
-
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\H{o}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}$.<br />Comment: 25 pages, 9 figures
- Subjects :
- Mathematics - Combinatorics
05C10, 05C69
Subjects
Details
- Database :
- arXiv
- Journal :
- Electronic Journal of Combinatorics. Vol. 23(3), 2016, #P3.45
- Publication Type :
- Report
- Accession number :
- edsarx.1609.06010
- Document Type :
- Working Paper