##
**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 X_{n} is defined as the maximal size of a clique in such a random graph; various results concerning X_{n} 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