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 Gn does not contain a cycle C2k+1 for 3 \leq k \leq r then Gn contains at least (1-\epsilon)n1-1/r independent vertices if n > n\epsilon; and, there is a positive function f(c) such that if a graph Gn has at least cn2 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