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