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 Kr, 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 Cn, where n is odd or even. A typical result is given by 2kn < r(C2n+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