Options
Large independent sets in triangle-free planar graphs
Publikationstyp
Conference Paper
Date Issued
2014
Sprache
English
Author(s)
TORE-URI
First published in
Number in series
8737 LNCS
Volume
8737
Start Page
346
End Page
357
Citation
22nd Annual European Symposium on Algorithms (ESA 2014)
Contribution to Conference
Publisher DOI
Scopus ID
Publisher
Springer
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 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-ε).
DDC Class
004: Informatik