2018/08/04 by Yongxin Lan, Yongtang Shi, Lan, Yongxin +3 · 3 citations
Computer Science · Mathematics · #05C10 #05C35 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1808.01487
openalex publication_date 2018/08/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given a graph H, a graph is H-free if it does not contain H as a subgraph. We continue to study the topic of "extremal" planar graphs, that is, how many edges can an H-free planar graph on n vertices have? We define exP(n,H) to be the maximum number of edges in an H-free planar graph on n vertices. We first obtain several sufficient conditions on H which yield exP(n,H)=3n-6 for all n≥ |V(H)|. We discover that the chromatic number of H does not play a role, as in the celebrated Erdős-Stone Theorem. We then completely determine exP(n,H) when H is a wheel or a star. Finally, we examine the case when H is a (t, r)-fan, that is, H is isomorphic to K1+tKr-1, where t≥2 and r≥ 3 are integers. However, determining exP(n,H), when H is a planar subcubic graph, remains wide open.