Tree densities in sparse graph classes

DOI10.4153/S0008414X21000316zbMATH Open1506.90260arXiv2009.12989OpenAlexW3088292866MaRDI QIDQ5046563FDOQ5046563

Tony Huynh, David R. Wood

Publication date: 8 November 2022

Published in: Canadian Journal of Mathematics (Search for Journal in Brave)

Abstract: What is the maximum number of copies of a fixed forest $T$ in an $n$-vertex graph in a graph class $mathcalG$ as $noinfty$? We answer this question for a variety of sparse graph classes $mathcalG$. In particular, we show that the answer is $Theta(n^{alph{a}_d(T)})$ where $alph{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 $mathcalG$. For example, when $mathcalG$ is the class of $k$-degenerate graphs then $d=k$; when $mathcalG$ is the class of graphs containing no $K_{s,t}$-minor ($tgeqs$) then $d=s-1$; and when $mathcalG$ 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.

Full work available at URL: https://arxiv.org/abs/2009.12989

Recommendations

• Many \(T\) copies in \(H\)-free graphs
• Many \(T\) copies in \(H\)-free graphs
• Many H-copies in graphs with a forbidden tree
• Subtrees and subforests of graphs
• Generalized Turán number for linear forests

zbMATH Keywords

sparsitytreesextremal combinatoricsgraph minors

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05) Graph minors (05C83)

Cites Work

• Title not available (Why is that?)
• On the structure of linear graphs
• Bounded-degree independent sets in planar graphs
• Homomorphiesätze für Graphen
• On the degrees of the vertices of a directed graph
• Graphs on surfaces
• An extremal function for contractions of graphs
• Title not available (Why is that?)
• Two problems on independent sets in graphs
• Lower bound of the Hadwiger number of graphs by their average degree
• Light edges in degree-constrained graphs
• An entropy approach to the hard-core model on bipartite graphs
• Intersection Theorems for Systems of Sets
• Sparsity. Graphs, structures, and algorithms
• Quickly excluding a forest
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• Knots and links in spatial graphs
• Title not available (Why is that?)
• Rank-width and tree-width of \(H\)-minor-free graphs
• The maximum number of triangles in a \(K_4\)-free graph
• A new Turán-type theorem for cliques in graphs
• On the number of cliques in graphs with a forbidden minor
• The maximum number of complete subgraphs in a graph with given maximum degree
• Proper minor-closed families are small
• A linear-time algorithm to find a separator in a graph excluding a minor
• Small complete minors above the extremal edge density
• Number of Cliques in Graphs with a Forbidden Subdivision
• On the number of cycles of lengthk in a maximal planar graph
• Small minors in dense graphs
• Independent sets in graphs with given minimum degree
• Maximizing the Number of Independent Sets of a Fixed Size
• Counting Independent Sets of a Fixed Size in Graphs with a Given Minimum Degree
• Title not available (Why is that?)
• On the Number of Cliques in Graphs with a Forbidden Subdivision or Immersion
• Extremal problems for independent set enumeration
• On the maximum number of cliques in a graph embedded in a surface
• A Kruskal-Katona type theorem for graphs
• On the maximum number of cliques in a graph
• Logarithmically small minors and topological minors
• The maximum number of cliques in dense graphs
• Knots in certain spatial graphs
• Knots and links in spatial graphs: a survey
• Sur un nouvel invariant des graphes et un critère de planarité. (On a new graph invariant and a planarity criterion)
• Title not available (Why is that?)
• Approximation algorithms for independent sets in map graphs
• Map graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Sachs' linkless embedding conjecture
• Title not available (Why is that?)
• On the Colin de Verdière number of graphs
• Many \(T\) copies in \(H\)-free graphs
• Recognizing string graphs is decidable
• Das Geschlecht des vollständigen paaren Graphen
• Bounds on the number of complete subgraphs
• How many \(F\)'s are there in \(G\)?
• Many, many more intrinsically knotted graphs
• The maximum number of cliques in graphs without long cycles
• An annotated bibliography on 1-planarity
• Parameters Tied to Treewidth
• Improved bounds for the sunflower lemma
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Maximum Number of Complete Subgraphs of Fixed Size in a Graph with Given Maximum Degree
• Structure of Graphs with Locally Restricted Crossings
• On low tree-depth decompositions
• New bounds on the edge number of ak-map graph
• Note on sunflowers
• A new proof of the Fisher-Ryan bounds for the number of cliques of a graph
• Connectivity, graph minors, and subgraph multiplicity
• The maximum number of triangles in a graph of given maximum degree
• A note on the maximum number of triangles in a C₅‐free graph
• Bounds on the number of cycles of length three in a planar graph
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the frequency of 3-connected subgraphs of planar graphs
• Intrinsically knotted graphs
• Many cliques in \(H\)-free subgraphs of random graphs
• Generalized Turán problems for disjoint copies of graphs
• Separating 3-cycles in plane triangulations
• \(H\)-free subgraphs of dense graphs maximizing the number of cliques and their blow-ups
• Gap-planar graphs
• Generalized Turán problems for even cycles
• Many triangles with few edges
• Some sharp results on the generalized Turán numbers
• Counting copies of a fixed subgraph in \(F\)-free graphs
• The maximum number of $P_\ell$ copies in $P_k$-free graphs
• Many H-Copies in Graphs with a Forbidden Tree
• Title not available (Why is that?)
• Defective colouring of graphs excluding a subgraph or minor
• On the number of cycles of length 4 in a maximal planar graph
• Title not available (Why is that?)
• A tight Erdős-Pósa function for planar minors

Cited In (8)

• Graph theory. Abstracts from the workshop held January 2--8, 2022
• Singular σ-dense trees
• Bounding the number of odd paths in planar graphs via convex optimization
• Subgraph densities in a surface
• Treewidth, Circle Graphs, and Circular Drawings
• The maximum number of pentagons in a planar graph
• VC-density for trees
• Shallow Minors, Graph Products, and Beyond-Planar Graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5046563)