##
**Zentralblatt MATH**

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

**Zbl.No: ** 324.05124

**Autor: ** Erdös, Paul; Graham, Ronald L.

**Title: ** On partition theorems for finite graphs. (In English)

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

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

For a finite graph G and positive integer k, let r(G; k) denote the least integer r such that if the edges of K_{r}, the complete graph on r vertices are arbitrarily partitioned into k classes then some class contains a subgraph isomorphic to G. The existence of r(G; k) follows from the well known theorem of Ramsey. In this paper, the authors have investigated the behavior of r(G; k) for various classes of graphs including trees, forests and cycles C_{n}, where n is odd or even. A typical result is given by 2^{k}n < r(C_{2n+1}; k) < 2(k+2)!n.

**Reviewer: ** M.S.Cheema

**Classif.: ** * 05C99 Graph theory

05C35 Extremal problems (graph theory)

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag