4 Large Independent Sets in Triangle-Free Planar Graphs∗
Matthias Mnich · 2014
Every triangle-free planar graph on n vertices has an independent set of size at least (n + 1)/3, and this lower bound is tight. We give an algorithm that, given a triangle-free planar graph G on n vertices and an integer k ≥ 0, decides whether G has an independent set of size at least (n + k)/3, in time $2^{O(\sqrt{k})}n$ . Thus, the problem is fixed-parameter tractable when parameterized by k. Furthermore, as a corollary of the result used to prove the correctness of the algorithm, we show that there exists ε > 0 such that every planar graph of girth at least five on n vertices has an independent set of size at least n/(3 − ε).