What is the maximum number of copies of a fixed forest T in an n-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 T induced by the vertices of degree at most d, for some integer d that depends on. For example, when is the class of k-degenerate graphs then; when is the class of graphs containing no -minor then; and when is the class of k-planar graphs then. All these results are in fact consequences of a single lemma in terms of a finite set of excluded subgraphs.

Tree densities in sparse graph classes / Huynh, T.; Wood, D. R.. - In: CANADIAN JOURNAL OF MATHEMATICS-JOURNAL CANADIEN DE MATHEMATIQUES. - ISSN 0008-414X. - 74:5(2022), pp. 1385-1404. [10.4153/S0008414X21000316]

Tree densities in sparse graph classes

Huynh T.;
2022

Abstract

What is the maximum number of copies of a fixed forest T in an n-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 T induced by the vertices of degree at most d, for some integer d that depends on. For example, when is the class of k-degenerate graphs then; when is the class of graphs containing no -minor then; and when is the class of k-planar graphs then. All these results are in fact consequences of a single lemma in terms of a finite set of excluded subgraphs.
2022
Extremal combinatorics; graph minors; sparsity; trees
01 Pubblicazione su rivista::01a Articolo in rivista
Tree densities in sparse graph classes / Huynh, T.; Wood, D. R.. - In: CANADIAN JOURNAL OF MATHEMATICS-JOURNAL CANADIEN DE MATHEMATIQUES. - ISSN 0008-414X. - 74:5(2022), pp. 1385-1404. [10.4153/S0008414X21000316]
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1705883
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 6
social impact