##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 422.05039

**Autor: ** Erdös, Paul

**Title: ** Some extremal problems on families of graphs and related problems. (In English)

**Source: ** Comb. Math., Proc. int. Conf., Canberra 1977, Lect. Notes Math. 686, 13- 21 (1978).

**Review: ** [For the entire collection see Zbl 384.00005.]

The author proves the following two theorems: If a graph G_{n} does not contain a cycle C_{2k+1} for 3 \leq k \leq r then G_{n} contains at least (1-\epsilon)n^{1-1/r} independent vertices if n > n_{\epsilon}; and, there is a positive function f(c) such that if a graph G_{n} has at least cn^{2} edges, then it contains a refinement of a complete k-graph where k > f(c)n^{ ½}. He also summarizes the progress made on a number of open extremal problems.

**Reviewer: ** J.W.Moon

**Classif.: ** * 05C35 Extremal problems (graph theory)

00A07 Problem books

**Keywords: ** cycle; independent vertices; refinement

**Index Words: ** Problems

**Citations: ** Zbl.384.00005

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag