Ramsey theorems for multiple copies of graphs

Authors:
S. A. Burr, P. Erdős and J. H. Spencer

Journal:
Trans. Amer. Math. Soc. **209** (1975), 87-99

MSC:
Primary 05C15

DOI:
https://doi.org/10.1090/S0002-9947-1975-0409255-0

MathSciNet review:
0409255

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: If and are graphs, define the *Ramsey number* to be the least number such that if the edges of the complete graph are colored red and blue (say), either the red graph contains as a subgraph or the blue graph contains . Let denote the union of disjoint copies of . The following result is proved: Let and have and points respectively and have point independence numbers of and respectively. Then , where and where is an effectively computable function of and . The method used permits exact evaluation of for various choices of and , especially when or . In particular, when .

**[1]**V. Chvátal and F. Harary,*Generalized Ramsey theory for graphs*. Bull. Amer. Math. Soc.**78**(1972), 423-426. MR**45**#110. MR**0291016 (45:110)****[2]**S. A. Burr,*Generalized Ramsey theory for graphs a survey*, Graphs and Combinatorics, R. Bari and F. Harary, eds., Lecture Notes in Math., vol. 406, Springer-Verlag, Berlin and New York, 1974, pp. 52-75. MR**0379210 (52:116)****[3]**F. Harary,*Graph theory*, Addison-Wesley, Reading, Mass., 1969. MR**41**#1566. MR**0256911 (41:1566)****[4]**E. J. Cockayne,*An application of Ramsey's theorem*, Canad. Math. Bull.**13**(1970), 145-146. MR**41**#6721. MR**0262111 (41:6721)****[5]**J. W. Moon,*Disjoint triangles in chromatic graphs*, Math. Mag.**39**(1966), 259-261. MR**35**#4123. MR**0213259 (35:4123)****[6]**V. Chvátal and F. Harary,*Generalized Ramsey numbers for graphs*. II:*Small diagonal numbers*, Proc. Amer. Math. Soc.**32**(1972), 389-394. MR**0332559 (48:10886)****[7]**S. A. Burr,*Diagonal Ramsey numbers for small graphs*(to appear). MR**693021 (84g:05103)****[8]**V. Chvátal and F. Harary,*Genveralized Ramsey theory for graphs*. III:*Small offdiagonal numbers*, Pacific J. Math.**41**(1972), 335-345. MR**47**#3248. MR**0314696 (47:3248)****[9]**S. A. Burr and J. A. Roberts,*On Ramsey numbers for Linear forests*, Discrete Math.**8**(1974), 245-250. MR**0335325 (49:107)**

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC:
05C15

Retrieve articles in all journals with MSC: 05C15

Additional Information

DOI:
https://doi.org/10.1090/S0002-9947-1975-0409255-0

Article copyright:
© Copyright 1975
American Mathematical Society