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 Free Access

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?)


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