##
**Zentralblatt MATH**

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

**Zbl.No: ** 316.05110

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

**Title: ** On the magnitude of generalized Ramsey numbers for graphs. (In English)

**Source: ** Infinite finite Sets, Colloq. Honour Paul Erdös, Keszthely 1973, Colloq. Math. Soc. Janos Bolyai 10, 215-240 (1975).

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

Let G and H be graphs and let r(G,H) be the least number so that any edge 2-coloring of K_{p} (the complete graph on p vertices) with p \geq r(G,H) contains either a subgraph isomorphic with G all of whose edges are colored with the first color or a subgraph isomorphic with H all of whose edges are colored with the second color. We let r(G) denote r(G,G). This paper is devoted to a study of the asymptotic properties of the functions r(G,H) and r(G). Central to this discussion is the concept of an L-set: A set **{**G_{1},G_{2}, ... **}** of graphs is called an L-set if there is a constant c so that r(G_{i}) \leq c · p(G_{i}), for all i, where p(G_{i}) denotes the number of vertices of G_{i}. Also a set of ordered pairs **{**(G_{1},H_{1}),(G_{2},H_{2}), ... **}** of graphs is called an L-set if there is a constant c so that r(G_{i},H_{i}) \leq c · (p(G_{i})+p(H_{i})), for all i. Many special cases of, and results related to, the following conjecture are proved in this paper. Conjecture: Any set of graphs or pairs of graphs having bounded arboricity is an L-set. For example Theorem 3.1. Suppose **{**G_{1},G_{2}, ... **}** is an L-set having bounded arboricity. Then **{**G_{1}+K_{1},G_{2}+K_{1}, ... **}** is an L-set. Theorem 3.5. If n \geq r(K_{k}), k \geq 2 and G denotes the graph K_{k} \cup (n-k)K_{1}, then for some absolute constant c, k_{n}+1 \leq r(G+K_{1}) \leq kn+cn/k. Theorem 4.1. There exist graphs **{**G_{1},G_{2}, ... **}** and **{**H_{1},H_{2}, ... **}** such that **{**(G_{1},H_{1})(G_{2},H_{2}), ... **}** is an L-set but **{**G_{1},G_{2}, ... **}** and **{**H_{1},H_{2}, ... **}** are no L-sets.

**Reviewer: ** J.E.Graver

**Classif.: ** * 05C15 Chromatic theory of graphs and maps

05C35 Extremal problems (graph theory)

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag