Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

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 $ G$ and $ H$ are graphs, define the Ramsey number $ r(G,H)$ to be the least number $ p$ such that if the edges of the complete graph $ {K_p}$ are colored red and blue (say), either the red graph contains $ G$ as a subgraph or the blue graph contains $ H$. Let $ mG$ denote the union of $ m$ disjoint copies of $ G$. The following result is proved: Let $ G$ and $ H$ have $ k$ and $ l$ points respectively and have point independence numbers of $ i$ and $ j$ respectively. Then $ N - 1 \leqslant r(mG,nH) \leqslant N + C$, where $ N = km + ln - min(mi,mj)$ and where $ C$ is an effectively computable function of $ G$ and $ H$. The method used permits exact evaluation of $ r(mG,nH)$ for various choices of $ G$ and $ H$, especially when $ m = n$ or $ G = H$. In particular, $ r(m{K_3},n{K_3}) = 3m + 2n$ when $ m \geqslant n,m \geqslant 2$.


References [Enhancements On Off] (What's this?)

  • [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)

Similar Articles

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

American Mathematical Society