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 initiated by Dowden [J. Graph Theory 83 (2016) 213–230], that is, how many edges can an $H$-free planar graph on $n$ vertices have? We define $ex_{_\mathcal{P}}(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 $ex_{_\mathcal{P}}(n,H)=3n-6$ for all $n\ge |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 $ex_{_\mathcal{P}}(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 $K_1+tK_{r-1}$, where $t\ge2$ and $r\ge 3$ are integers. However, determining $ex_{_\mathcal{P}}(n,H)$, when $H$ is a planar subcubic graph, remains wide open.
@article{10_37236_8255,
author = {Yongxin Lan and Yongtang Shi and Zi-Xia Song},
title = {Extremal {\(H\)-free} planar graphs},
journal = {The electronic journal of combinatorics},
year = {2019},
volume = {26},
number = {2},
doi = {10.37236/8255},
zbl = {1412.05051},
url = {http://geodesic.mathdoc.fr/articles/10.37236/8255/}
}
TY - JOUR
AU - Yongxin Lan
AU - Yongtang Shi
AU - Zi-Xia Song
TI - Extremal \(H\)-free planar graphs
JO - The electronic journal of combinatorics
PY - 2019
VL - 26
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/8255/
DO - 10.37236/8255
ID - 10_37236_8255
ER -
%0 Journal Article
%A Yongxin Lan
%A Yongtang Shi
%A Zi-Xia Song
%T Extremal \(H\)-free planar graphs
%J The electronic journal of combinatorics
%D 2019
%V 26
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/8255/
%R 10.37236/8255
%F 10_37236_8255
Yongxin Lan; Yongtang Shi; Zi-Xia Song. Extremal \(H\)-free planar graphs. The electronic journal of combinatorics, Tome 26 (2019) no. 2. doi: 10.37236/8255
