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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page