TY - JOUR
T1 - Ramsey theorems for multiple copies of graphs
AU - Burr, S. A.
AU - Erdös, P.
AU - Spencer, J. H.
PY - 1975
Y1 - 1975
N2 - 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 Kpare 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 ≤ r(mG, nH) ≤ N + C, where N = km + In - min (mi, mj) and where C is an effectively computable function of G and H. The method used permits exact evaluation of r(mGt nH) for various choices of G and H, especially when m — n or G-H. In particular, r(mK3, nK3) = 3m + 2n when m ≥ n, m ≥ 2.
AB - 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 Kpare 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 ≤ r(mG, nH) ≤ N + C, where N = km + In - min (mi, mj) and where C is an effectively computable function of G and H. The method used permits exact evaluation of r(mGt nH) for various choices of G and H, especially when m — n or G-H. In particular, r(mK3, nK3) = 3m + 2n when m ≥ n, m ≥ 2.
UR - http://www.scopus.com/inward/record.url?scp=0003164032&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0003164032&partnerID=8YFLogxK
U2 - 10.1090/S0002-9947-1975-0409255-0
DO - 10.1090/S0002-9947-1975-0409255-0
M3 - Article
AN - SCOPUS:0003164032
SN - 0002-9947
VL - 209
SP - 87
EP - 99
JO - Transactions of the American Mathematical Society
JF - Transactions of the American Mathematical Society
ER -