Generalized Turán results for disjoint copies of degenerate graphs

2025/08/08 by Caihong Yang, Jiasheng Zeng, Yang, Caihong +1
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2508.06043

openalex publication_date 2025/08/08 · openalex created_date 2025/10/15 · openalex updated_date 2026/07/28

Abstract

The generalized Turán number ex(n, H, F) denotes the maximum number of copies of H in an n-vertex F-free graph. For an integer t ≥ 1, let tF be the vertex-disjoint union of t copies of F. Gerbner, Methuku, and Vizer (2019) established an asymptotically sharp bound for ex(n,K_r,(t+1)K_2,b). We extend their results in two directions by considering forbidden graphs (t+1)K_a,b and (t+1)C_2k and establish more precise matching upper and lower bounds of the same order of magnitude.

Citations

• Survey of generalized Turán problems -- counting subgraphs
• The maximum number of cliques in disjoint copies of graphs
• Generalized Turán problem for a path and a clique
• Clique Supersaturation
• Counting cliques without generalized theta graphs
• Counting triangles in graphs without vertex disjoint odd cycles
• On the generalized Turán problem for odd cycles
• Maximum cliques in a graph without disjoint given subgraph
• The maximum number of triangles in F_k-free graphs
• Generalized Turán problems for K_2,t
• Generalized Tur'an problems for even cycles
• Generalized Turán problems for disjoint copies of graphs
• The maximum number of cliques in graphs without long cycles
• The history of degenerate (bipartite) extremal graph problems

Related

• Generalized Turán results for disjoint cliques
• Generalized Turán problems for disjoint copies of graphs
• Some exact results for non-degenerate generalized Turán problems
• Maximum cliques in a graph without disjoint given subgraph
• Generalized Turán results for matchings