Publications of (and about) Paul Erdös
Autor: Erdös, Paul
Title: Some recent progress on extremal problems in graph theory. (In English)
Source: Proc. 6th southeast. Conf. Comb., Graph Theor., Comput.; Boca Raton 1975, 3-14 (1975).
Review: This is one in a series of the author's ``Problems and Results'' papers on extremal graph theory. Almost the entire paper is devoted to one particular theme. Let G be a graph, and let f(n,G) denote the smallest integer such that every graph on n vertices with at least f(n,G) edges will contain G as a subgraph. Bounds for f(n,G) for various types of G are given, including circuits (C4 receiving particular attention), bipartite graphs and regular graphs. Some of the problems are treated in reasonable detail, while others are simply stated. An extensive bibliography is given.
Classif.: * 05C35 Extremal problems (graph theory)
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag