2024/12/19 by Marco D’Elia, Fabrizio Frati, D'Elia, Marco +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2412.14784
openalex publication_date 2024/12/19 · openalex created_date 2024/12/21 · openalex updated_date 2026/07/28
In this paper, we study the following question. Let \mathcal 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 \mathcal 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 a large induced linear forest, or a large induced 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 \mathcal 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 (5n)/(13)>0.384n vertices, and that there exist n-vertex planar graphs whose largest induced subgraph with degree at most 3 has (4n)/(7)+O(1)<0.572n+O(1) vertices.