Exact Clique Counts in Graphs with a Forbidden Tree
Abstract
For a fixed tree T on t vertices, let ex(n,Kr,T) denote the maximum number of r-cliques in an n-vertex T-free graph. Write n=α(t−1)+β with 0≤β<t−1. A conjecture proposed in extremal-graph form by Alon and Shikhelman~\cite{alon2016}, later stated explicitly as an exact clique-counting formula by Gerbner and Palmer~\cite{GP2026}, asserts that ex(n,Kr,T)=αbinomt−1r+binomβr, with the extremal construction given by the vertex disjoint union of α copies of Kt−1 and a graph with β vertices. This paper proves this conjecture for every n and for every tree T whenever Clog t≤ r≤ t−1 and t is sufficiently large, where C is an absolute constant. This lowers the previously known general threshold r≥⌈(2t−1)/3⌉, which is linear in t to logarithmic order. The paper also proves the conjecture for every 3≤ r≤ t−1 when at least ⌈(t−3)/2⌉ leaves of T have a common neighbor, and this extends the known results for stars and double stars.
Related
- Range of Clique Counts in Graphs
- Characterizing chordal llcorner-EPG graphs via admissible clique tree orientations
- Clique counts under degree and matching constraints
- Clique-dependent strongly sublinear treewidth and strongly sublinear tree-independence number
- A finite forbidden family with superlinear surplus and non-join extremal graphs
BibTeX
@misc{zhao2026exact,
title = {{Exact Clique Counts in Graphs with a Forbidden Tree}},
author = {XiaoJun Zhao and YueJian Peng},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.25746},
eprint = {2608.25746},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.25746},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Exact Clique Counts in Graphs with a Forbidden Tree
AU - XiaoJun Zhao
AU - YueJian Peng
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2608.25746
UR - https://arxiv.org/abs/2608.25746
AB - For a fixed tree T on t vertices, let ex(n,K_r,T) denote the maximum number of r-cliques in an n-vertex T-free graph. Write n=α(t−1)+β with 0≤β<t−1. A conjecture proposed in extremal-graph form by Alon and Shikhelman~\cite{alon2016}, later stated explicitly as an exact clique-counting formula by Gerbner and Palmer~\cite{GP2026}, asserts that ex(n,K_r,T)=αbinomt−1r+binomβr, with the extremal construction given by the vertex disjoint union of α copies of K_t−1 and a graph with β vertices. This paper proves this conjecture for every n and for every tree T whenever Clog t≤ r≤ t−1 and t is sufficiently large, where C is an absolute constant. This lowers the previously known general threshold r≥⌈(2t−1)/3⌉, which is linear in t to logarithmic order. The paper also proves the conjecture for every 3≤ r≤ t−1 when at least ⌈(t−3)/2⌉ leaves of T have a common neighbor, and this extends the known results for stars and double stars.
ER -