Large Induced Subgraphs of Bounded Degree in Outerplanar and Planar Graphs

In this paper, we study the following question. Let G be a family of planar graphs and let k≥3 be an integer. What is the largest value fk(n) such that every n-vertex graph in G has an induced subgraph with degree at most k and with fk(n) vertices? Similar questions, in which one seeks a large induced forest, or linear forest, or d-degenerate graph, rather than a large induced graph of bounded degree, have been studied for decades and have given rise to some of the most fascinating and elusive conjectures in Graph Theory. We tackle our problem when G is the class of the outerplanar graphs or the class of the planar graphs. In both cases, we provide upper and lower bounds on the value of fk(n). For example, we prove that every n-vertex planar graph has an induced subgraph with degree at most 3 and with 5n13>0.384n vertices, and that there exist n-vertex planar graphs whose largest induced subgraph with degree at most 3 has 4n7+O(1)<0.572n+O(1) vertices.