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