Dvořák, ZdeněkZdeněkDvořákMnich, MatthiasMatthiasMnich2020-01-282020-01-282017SIAM Journal on Discrete Mathematics (2017)http://hdl.handle.net/11420/4610Every 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 2O(√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-ϵ). We further give an algorithm that, given a planar graph G of maximum degree 4 on n vertices and an integer k ≥ 0, decides whether G has an independent set of size at least (n + k)/4, in time 2O(√k)n. 7copy; 2017 Zdeňek Dvořák, Matthias Mnich.en1095-71462017213551373Society for Industrial and Applied MathematicsFixed-parameter tractabilityIndependent setPlanar graphsTreewidthConference Paper10.1137/16M10618621311.2749Other