##
**Zentralblatt MATH**

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

**Zbl.No: ** 745.05043

**Autor: ** Burr, Stefan A.; Erdös, Paul

**Title: ** Extremal non-Ramsey graphs. (In English)

**Source: ** Graph theory, combinatorics, algorithms, and applications, Proc. 2nd Int. Conf., San Francisco/CA (USA) 1989, 42-66 (1991).

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

Let *G* = (*G*_{1},... ,*G*_{k}) be a k-tuple of non-empty sets of graphs. For a graph F, the relation F ––> *G* indicates that, whenever the edges of F are colored with k colors, there is an index i and graph G in *G*_{i} so that there is a subgraph of F isomorphic to G with all edges assigned color i. Now let *F* be a family of graphs and define ex(n; *F*) to be the maximum number of edges that a graph on n vertices can have without containing a subgraph isomorphic to a graph in *F*. If *F* is the set of graphs F so that F\not ––> *G* we replace ex(n,*F*) with ex(n; \not ––> *G*).

Starting with the simple upper bound: ex(n; \not ––> *G*) \leq **sum**_{1 \leq i \leq h}ex(n; *G*_{i}) the authors prove a variety of interesting equalities and inequalities about ex(n; \not ––> *G*).

**Reviewer: ** J.E.Graver

**Classif.: ** * 05C75 Structural characterization of types of graphs

05C55 Generalized Ramsey theory

05C35 Extremal problems (graph theory)

**Citations: ** Zbl 734.00014

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag