In this paper, we study the following question. Let  \(\mathcal G\) be a family of planar graphs and let  \(k\ge 3\) be an integer. What is the largest value  \(f_k(n)\) such that every n-vertex graph in  \(\mathcal G\) has an induced subgraph with degree at most k and with  \(f_k(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  \(\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  \(f_k(n)\) . For example, we prove that every n-vertex planar graph has an induced subgraph with degree at most 3 and with  \(\frac{5n}{13}>0.384n\) vertices, and that there exist n-vertex planar graphs whose largest induced subgraph with degree at most 3 has  \(\frac{4n}{7}+O(1)<0.572n+O(1)\) vertices.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Large Induced Subgraphs of Bounded Degree in Outerplanar and Planar Graphs

  • Marco D’Elia,
  • Fabrizio Frati

摘要

In this paper, we study the following question. Let  \(\mathcal G\) be a family of planar graphs and let  \(k\ge 3\) be an integer. What is the largest value  \(f_k(n)\) such that every n-vertex graph in  \(\mathcal G\) has an induced subgraph with degree at most k and with  \(f_k(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  \(\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  \(f_k(n)\) . For example, we prove that every n-vertex planar graph has an induced subgraph with degree at most 3 and with  \(\frac{5n}{13}>0.384n\) vertices, and that there exist n-vertex planar graphs whose largest induced subgraph with degree at most 3 has  \(\frac{4n}{7}+O(1)<0.572n+O(1)\) vertices.