Tree densities in sparse graph classes

Huynh, Tony ; Wood, David R.

Canadian journal of mathematics, Tome 74 (2022) no. 5, pp. 1385-1404

Résumé

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.

Détail

DOI : 10.4153/S0008414X21000316

Mots-clés : Extremal combinatorics, trees, graph minors, sparsity