What is the maximum number of copies of a fixed forest $T$ in an $n$-vertex graph in a graph class $mathcal{G}$ as $nto infty$? We answer this question for a variety of sparse graph classes $mathcal{G}$. In particular, we show that the answer is $Theta(n^{alpha_d(T)})$ where $alpha_d(T)$ is the size of the largest stable set in the subforest of $T$ induced by the vertices of degree at most $d$, for some integer $d$ that depends on $mathcal{G}$. For example, when $mathcal{G}$ is the class of $k$-degenerate graphs then $d=k$; when $mathcal{G}$ is the class of graphs containing no $K_{s,t}$-minor ($tgeq s$) then $d=s-1$; and when $mathcal{G}$ is the class of $k$-planar graphs then $d=2$. All these results are in fact consequences of a single lemma in terms of a finite set of excluded subgraphs.
تحميل البحث