Tree densities in sparse graph classes
arXiv:2009.12989 · doi:10.4153/S0008414X21000316
Abstract
What is the maximum number of copies of a fixed forest in an -vertex graph in a graph class as ? We answer this question for a variety of sparse graph classes . In particular, we show that the answer is where is the size of the largest stable set in the subforest of induced by the vertices of degree at most , for some integer that depends on . For example, when is the class of -degenerate graphs then ; when is the class of graphs containing no -minor () then ; and when is the class of -planar graphs then . All these results are in fact consequences of a single lemma in terms of a finite set of excluded subgraphs.
References in corpus (21)
- An annotated bibliography on 1-planarity
- Counting copies of a fixed subgraph in -free graphs
- On the maximum number of cliques in a graph
- On Low Tree-Depth Decompositions
- Defective colouring of graphs excluding a subgraph or minor
- Rank-width and Tree-width of H-minor-free Graphs
- Note on Sunflowers
- Maximizing the number of independent sets of a fixed size
- Many, many more intrinsically knotted graphs
- Subgraph densities in a surface
- Logarithmically-small Minors and Topological Minors
- The maximum number of cliques in a graph embedded in a surface
- Small Minors in Dense Graphs
- Clustered Graph Coloring and Layered Treewidth
- Number of cliques in graphs with a forbidden subdivision
- A tight Erdős-Pósa function for planar minors
- The Maximum Number of Pentagons in a Planar Graph
- Homomorphism counts in robustly sparse graphs
- The maximum number of copies in -free graphs
- Graph product structure for non-minor-closed classes
- The Maximum Number of Paths of Length Three in a Planar Graph