Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 344.05155
Autor: Bollobás, Béla; Erdös, Paul
Title: Cliques in random graphs. (In English)
Source: Math. Proc. Camb. Philos. Soc. 80, 419-427 (1976).
Review: The paper concerns random graphs. A random graph is defined here as a graph whose vertex set is the set of all positive integers and in which each edge occurs with the probability p (this probability is the same for all pairs of vertices). A random variable Xn is defined as the maximal size of a clique in such a random graph; various results concerning Xn are proved. Further the existence of infinite cliques in a random graph and the number of colours necessary for colouring a random graph by means of the so-called greedy algorithm are investigated. A remark on hypergraphs is added.
Reviewer: B.Zelinka
Classif.: * 05C99 Graph theory
60C05 Combinatorial probability
05C35 Extremal problems (graph theory)
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag