The number of graphs with large forbidden subgraphs

2010/01/24 by Béla Bollobás, Bollobas, Bela, Vladimir Nikiforov +1
Computer Science · Mathematics · #05C35 #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1001.4249

openalex publication_date 2010/01/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this note, extending some results of Erdos, Frankl, Rodl, Alexeev, Bollobas and Thomason we determine asymptotically the number of graphs which do not contain certain large subgraphs. In particular, if H₁,...,H_n,... are graphs with chromatic numbers r₁,...,r_n,... and order o(log n), we dermine asymptotically the number of graphs of order n not containing H_n as a subgraph. We also give similar results for induced subgraphs.

Citations

• On extremal problems of graphs and generalized graphs

Related

• Stability for large forbidden subgraphs
• The largest subgraph without a forbidden induced subgraph
• Extremal problems in ordered graphs
• On the Tight Chromatic Bounds for a Class of Graphs without Three Induced Subgraphs
• Finite subgraphs of uncountably chromatic graphs