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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page