Tree densities in sparse graph classes

Abstract What is the maximum number of copies of a fixed forest T in an n -vertex graph in a graph class $\mathcal {G}$ as $n\to \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 ( $t\geqslant 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.