##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 782.05072

**Autor: ** Bollobás, Béla; Erdös, Paul; Spencer, Joel; West, Douglas B.

**Title: ** Clique coverings of the edges of a random graph. (In English)

**Source: ** Combinatorica 13, No.1, 1-5 (1993).

**Review: ** Bounds on the clique number of the random graph (with the edge probability of ½) are derived. It is proved that almost every graph with n vertices has a collection of O(n^{2} ln\ln n/(ln n)^{2}) cliques that cover all its edges. It is also proved that for almost every graph with n vertices, in order to cover all its edges it is necessary to use at least (1-\epsilon)n^{2}/(2 ln n)^{2} cliques.

**Reviewer: ** M.Truszczynski (Lexington)

**Classif.: ** * 05C80 Random graphs

05C70 Factorization, etc.

**Keywords: ** interval number; intersection number; clique number; random graph

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag