Publisher DOI: 10.1007/978-3-662-44777-2_29
Title: Large independent sets in triangle-free planar graphs
Language: English
Authors: Dvořák, Zdeněk 
Mnich, Matthias  
Issue Date: 2014
Source: 22nd Annual European Symposium on Algorithms (ESA 2014)
Part of Series: Lecture notes in computer science 
Journal or Series Name: Lecture notes in computer science 
Abstract (english): 
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-ε).
Conference: 22nd Annual European Symposium on Algorithms (ESA 2014) 
URI: http://hdl.handle.net/11420/7627
ISBN: 978-366244776-5
ISSN: 0302-9743
Document Type: Chapter/Article (Proceedings)
Appears in Collections:Publications without fulltext

Show full item record

Page view(s)

30
Last Week
1
Last month
2
checked on Jan 17, 2021

Google ScholarTM

Check

Add Files to Item

Note about this record

Export

Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.