## Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  358.05027
Autor:  Erdös, Paul; Kleitman, Daniel J.; Rothschild, B.L.
Title:  Asymptotic enumeration of Kn-free graphs. (In English)
Source:  Colloq. int. Teorie comb., Roma 1973, Tomo II, 19-27 (1976).
Review:  [For the entire collection see Zbl 348.00004.]
This paper is devoted to the proofs of the following two results.
Result 1: Let Gk(n) be the number of graphs with n vertices and with no complete subgraphs on k vertices. Then log2(Gk(n)) = \frac{n2}2(1-\frac1{k-1})+O(n2).
Result 2: Let Tn be the number of graphs with n vertices and with no complete subgraphs on 3 vertices; let Sn be the number of bipartite graphs on n-vertices. Then

Tn = Sn(1+o( 1/n )).

Reviewer:  J.E.Graver
Classif.:  * 05C30 Enumeration of graphs and maps
05C35 Extremal problems (graph theory)

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag