Tree densities in sparse graph classes

What is the maximum number of copies of a fixed forest T in an n -vertex graph in a graph class G as n→ ∞ ? We answer this question for a variety of sparse graph classes G . In particular, we show that the answer is Θ (n^α d(T)) where α 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 G . For example, when G is the class of k -degenerate graphs then $d=k$ ; when G is the class of graphs containing no Ks,t -minor ( t s ) then $d=s-1$ ; and when 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.