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

Article copyright: © Copyright 1975 American Mathematical Society