A survey of what is known about maximizing the count of one fixed subgraph in graphs that avoid another fixed subgraph.
The maximum number of cliques in disjoint copies of graphs
1 Pith paper cite this work. Polarity classification is still indexing.
abstract
The problem of determining the maximum number of copies of $T$ in an $H$-free graph, for any graphs $T$ and $H$, was considered by Alon and Shikhelman. This is a variant of Tur\'{a}n's classical extremal problem. We show lower and upper bounds for the maximum number of $s$-cliques in a graph with no disjoint copies of arbitrary graph. We also determine the maximum number of $s$-cliques in an $n$-vertex graph that does not contain a disjoint union of $k$ paths of length two when $k=2,3$, or $s\geqslant k+2$, or $n$ is sufficiently large, this partly confirms a conjecture posed by Chen, Yang, Yuan, and Zhang \cite{2024Chen113974}.
citation-role summary
citation-polarity summary
fields
math.CO 1years
2025 1verdicts
CONDITIONAL 1roles
background 1polarities
unclear 1representative citing papers
citing papers explorer
-
Survey of generalized Tur\'an problems -- counting subgraphs
A survey of what is known about maximizing the count of one fixed subgraph in graphs that avoid another fixed subgraph.