Premium
Excluding Induced Subgraphs III: A General Asymptotic
Author(s) -
Prömel H. J.,
Steger A.
Publication year - 1992
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240030104
Subject(s) - combinatorics , mathematics , induced subgraph , clique number , graph , induced subgraph isomorphism problem , split graph , clique , discrete mathematics , class (philosophy) , chordal graph , line graph , 1 planar graph , computer science , voltage graph , vertex (graph theory) , artificial intelligence
In this article we study asymptotic properties of the class of graphs not containing a fixed graph H as an induced subgraph. In particular we show that the number Forb n ★( H ) of such graphs on n vertices is essentially determined by the number of subgraphs of a single graph. This implies thatWhere t(H) is a graph‐theoretic parameter generalizing the chromatic number and the clique covering number. This result complements a theorem of Erdös, Frankl, and Rödl [2] who showed that the number Forb n (H) of graphs on n vertices which do not contain H as a weak subgraph is given by