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

m a t h c a l G

as

n o i n f t y

? We answer this question for a variety of sparse graph classes

m a t h c a l G

. In particular, we show that the answer is

T h e t a (n^{a l p h a_{d} (T)})

where

a l p h a_{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

m a t h c a l G

. For example, when

m a t h c a l G

is the class of

k

-degenerate graphs then

d = k

; when

m a t h c a l G

is the class of graphs containing no

K_{s, t}

-minor (

t g e q s

) then

d = s - 1

; and when

m a t h c a l 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.

Recommendations

Cites work

Cited in

(9)

This page was built for publication: Tree densities in sparse graph classes