Publications of (and about) Paul Erdös
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).
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