论文标题
稀疏图类中的树密度
Tree densities in sparse graph classes
论文作者
论文摘要
$ n $ vertex图中的固定森林$ t $的最大副本是图形类别$ \ mathcal {g} $ as $ n \ to \ infty $？我们为各种稀疏图类$ \ mathcal {g} $回答这个问题。特别是，我们表明答案是$θ（n^{α_d（t））$，其中$α_d（t）$是最大$ d $的$ t $的$ t $的最大稳定量的大小，对于某些整数$ d $而言，它取决于$ \ nathcal $ \ nathcal $ \ nathcal {g} $。例如，当$ \ Mathcal {g} $是$ k $ - 定义图的类时，则$ d = k $;当$ \ Mathcal {g} $是包含no $ k_ {s，t} $的图类时 - $ t = geq s $），则$ d = s-1 $;当$ \ Mathcal {g} $是$ k $ - 平面图的类时，$ d = 2 $。所有这些结果实际上是单个引理的后果，就一组有限的排除子图表而言。
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 $Θ(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 $\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\geq 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.
