###### Options

# Large independent sets in triangle-free planar graphs

Publikationstyp

Conference Paper

Publikationsdatum

2014

Sprache

English

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-ε).