zbMATH — the first resource for mathematics

Cliques in random graphs. (English) Zbl 0344.05155
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

05C99 Graph theory
60C05 Combinatorial probability
05C35 Extremal problems in graph theory
Full Text: DOI
[1] Matula, Combinatory Mathematics and its Applications pp 356– (1970)
[2] Bollob?s, Math. Proc. Cambridge Philos. Soc. 79 pp 19– (1976)
[3] Erd?s, Publ. Math. Inst. Hung. A. Sci. 5 A pp 17– (1960)
[4] Grimmett, Math. Proc. Cambridge Philos. Soc. 77 pp 313– (1975)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.