Large Independent Sets in Triangle-Free Planar Graphs

2013/11/12 by Dvorak, Zdenek, Mnich, Matthias
#68R10 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2

paper · doi:10.48550/arxiv.1311.2749

Abstract

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 2^O(sqrtk)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 epsilon>0 such that every planar graph of girth at least five on n vertices has an independent set of size at least n/(3-epsilon).

Related

• Triangle-free planar graphs with small independence number
• Counting independent sets in triangle-free graphs
• Triangle-free graphs with the fewest independent sets
• Independence number in triangle-free graphs avoiding a minor
• Properties of nowhere dense graph classes related to independent set problem