Bounded-Degree Independent Sets in Planar Graphs

An independent set of a graph is a set of vertices without edges between them. Every planar graph has an independent set of size at least 14 n and there are planar graphs for which any independent set has size at most 14 n. In this paper similar bounds are provided for the problem of bounded-degree independent set, i.e., an independent set where additionally all vertices have degree less than a pre-specified bound D. Our upper and lower bounds match (up to a small constant) for D ≤ 16