## 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 = (G1,... ,Gk) 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 Gi 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 sum1 \leq i \leq hex(n; Gi)

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