Dvořák, ZdeněkZdeněkDvořákMnich, MatthiasMatthiasMnich2020-10-212020-10-21201422nd Annual European Symposium on Algorithms (ESA 2014)http://hdl.handle.net/11420/7627Every 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 20(√k). 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-ε).enInformatikConference Paper10.1007/978-3-662-44777-2_29Other