Large Independent Sets in Triangle-Free Planar Graphs

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 epsilon>0 such that every planar
graph of girth at least five on n vertices has an independent set of
size at least n/(3-epsilon).

(joint work with Zdenek Dvorak)