Ramsey theorems for multiple copies of graphs

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