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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page