   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: 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\$.

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

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

Retrieve articles in all journals with MSC: 05C15