2024/08/22 by Ruilin Shi, Fan Wei, Shi, Ruilin +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2408.12082
openalex publication_date 2024/08/22 · openalex created_date 2024/12/20 · openalex updated_date 2026/07/28
Alon and Shikhelman initiated the systematic study of a generalization of the extremal function. Motivated by algorithmic applications, the study of the extremal function ex(n, Kk, Kt-minor), i.e., the number of cliques of order k in Kt-minor free graphs on n vertices, has received much attention. In this paper, we determine essentially sharp bounds on the maximum possible number of cliques of order k in a Kt-minor free graph on n vertices. More precisely, we determine a function C(k,t) such that for each k < t with t-k≫ log2 t, every Kt-minor free graph on n vertices has at most n C(k, t)1+ot(1) cliques of order k. We also show this bound is sharp by constructing a Kt-minor-free graph on n vertices with C(k, t) n cliques of order k. This bound answers a question of Wood and Fox-Wei asymptotically up to ot(1) in the exponent except the extreme values when k is very close to t.