Article contents
Tree densities in sparse graph classes
Published online by Cambridge University Press: 29 June 2021
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.
MSC classification
- Type
- Article
- Information
- Copyright
- © Canadian Mathematical Society 2021
Footnotes
Research supported by the Australian Research Council.
References
![](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20221104022241444-0931:S0008414X21000316:S0008414X21000316_inline890.png?pub-status=live)
![](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20221104022241444-0931:S0008414X21000316:S0008414X21000316_inline891.png?pub-status=live)
![](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20221104022241444-0931:S0008414X21000316:S0008414X21000316_inline892.png?pub-status=live)
![](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20221104022241444-0931:S0008414X21000316:S0008414X21000316_inline893.png?pub-status=live)
![](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20221104022241444-0931:S0008414X21000316:S0008414X21000316_inline894.png?pub-status=live)
![](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20221104022241444-0931:S0008414X21000316:S0008414X21000316_inline895.png?pub-status=live)
![](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20221104022241444-0931:S0008414X21000316:S0008414X21000316_inline896.png?pub-status=live)
![](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20221104022241444-0931:S0008414X21000316:S0008414X21000316_inline897.png?pub-status=live)
![](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20221104022241444-0931:S0008414X21000316:S0008414X21000316_inline898.png?pub-status=live)
![](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20221104022241444-0931:S0008414X21000316:S0008414X21000316_inline899.png?pub-status=live)
![](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20221104022241444-0931:S0008414X21000316:S0008414X21000316_inline900.png?pub-status=live)
![](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20221104022241444-0931:S0008414X21000316:S0008414X21000316_inline901.png?pub-status=live)
![](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20221104022241444-0931:S0008414X21000316:S0008414X21000316_inline902.png?pub-status=live)
![](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20221104022241444-0931:S0008414X21000316:S0008414X21000316_inline903.png?pub-status=live)
![](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20221104022241444-0931:S0008414X21000316:S0008414X21000316_inline904.png?pub-status=live)
![](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20221104022241444-0931:S0008414X21000316:S0008414X21000316_inline905.png?pub-status=live)
![](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20221104022241444-0931:S0008414X21000316:S0008414X21000316_inline906.png?pub-status=live)
![](https://static.cambridge.org/binary/version/id/urn:cambridge.org:id:binary:20221104022241444-0931:S0008414X21000316:S0008414X21000316_inline907.png?pub-status=live)
- 6
- Cited by