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(n2 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)n2/(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