Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  163.18203
Autor:  Erdös, Pál
Title:  On cliques in graphs (In English)
Source:  Isr. J. Math. 4, 233-234 (1966).
Review:  A complete subgraph of a graph G is called a clique if it is not contained in any other complete subgraph of G. Let g(n) denote the maximum number of different sizes of cliques that can occur in a graph with n points: if logk n denotes the k-times iterated logarithm to the base 2 of n, let H = H(n) be the smallest integer such that logH n < 2. The author shows that g(n) \geq n- log n-H(n)-O(1). This extends an earlier result of the reviewer and L.Moser [Isr. J. Math. 3, 23-28 (1965; Zbl 144.23205)].
Reviewer:  J.W.Moon
Classif.:  * 05C35 Extremal problems (graph theory)
Index Words:  topology

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag