## Ramsey theorems for multiple copies of graphs

HTML articles powered by AMS MathViewer

- by S. A. Burr, P. Erdős and J. H. Spencer PDF
- Trans. Amer. Math. Soc.
**209**(1975), 87-99 Request permission

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

- Václav Chvátal and Frank Harary,
*Generalized Ramsey theory for graphs*, Bull. Amer. Math. Soc.**78**(1972), 423–426. MR**291016**, DOI 10.1090/S0002-9904-1972-12927-6 - Stefan A. Burr,
*Generalized Ramsey theory for graphs—a survey*, Graphs and combinatorics (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973) Lecture Notes in Mat., Vol. 406, Springer, Berlin, 1974, pp. 52–75. MR**0379210** - Frank Harary,
*Graph theory*, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London 1969. MR**0256911**, DOI 10.21236/AD0705364 - E. J. Cockayne,
*An application of Ramsey’s theorem*, Canad. Math. Bull.**13**(1970), 145–146. MR**262111**, DOI 10.4153/CMB-1970-032-5 - J. W. Moon,
*Disjoint triangles in chromatic graphs*, Math. Mag.**39**(1966), 259–261. MR**213259**, DOI 10.2307/2689007 - Václav Chvátal and Frank Harary,
*Generalized Ramsey theory for graphs. II. Small diagonal numbers*, Proc. Amer. Math. Soc.**32**(1972), 389–394. MR**332559**, DOI 10.1090/S0002-9939-1972-0332559-X - S. A. Burr,
*Diagonal Ramsey numbers for small graphs*, J. Graph Theory**7**(1983), no. 1, 57–69. MR**693021**, DOI 10.1002/jgt.3190070108 - Václav Chvátal and Frank Harary,
*Generalized Ramsey theory for graphs. III. Small off-diagonal numbers*, Pacific J. Math.**41**(1972), 335–345. MR**314696**, DOI 10.2140/pjm.1972.41.335 - Stefan A. Burr and John A. Roberts,
*On Ramsey numbers for linear forests*, Discrete Math.**8**(1974), 245–250. MR**335325**, DOI 10.1016/0012-365X(74)90136-8

## Additional Information

- © Copyright 1975 American Mathematical Society
- 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