##
**Zentralblatt MATH**

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

**Zbl.No: ** 333.05119

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

**Title: ** Extremal Ramsey theory for graphs. (In English)

**Source: ** Utilitas Math. 9, 247-258 (1976).

**Review: ** For graphs G and H the Ramsey number r(G,H) is the least integer p such that in any labelled partition of the complete graph on p vertices into two graphs on the p vertices having disjoint edge sets, either the first contains a copy of G or the second contains a copy of H. The number r(G,G) is denoted by r(G) and called a diagonal Ramsey number. If __G__ and __H__ are sets of graphs, the authors define exr (__G__) = **max**_{G in G}r(G) and exr(__G__,__H__) = **max**_{G in G, H in H} r(G,H). C_{n},G_{n},K_{n} respectively denote the following classes of graphs: connected on n vertices, n-vertex graphs without isolated vertices, and n-chromatic graphs. B_{k,l} is the set of connected bipartite graphs with maximal independent sets having k and l vertices. In the theorems of \S2 exr(C_{m},K_{n}) and exr(G_{m},K_{n}) are determined. \S3 is concerned with connected graphs with specified chromatic numbers. In the next section the values of exr(B_{k,l}) and exr(B_{k,l},B_{k,l}) are determined, also those of exr(C_{n}) and exr(C_{n},C_{n}). \S5 is concerned with inequalities for exr(G_{n}) and exr(G_{n},G_{n}). The paper closes with several open problems and conjectures.

**Reviewer: ** W.G.Brown

**Classif.: ** * 05C35 Extremal problems (graph theory)

05C15 Chromatic theory of graphs and maps

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag