Ramsey number of a connected triangle matching

Abstract

We determine the $2$-color Ramsey number of a {\em connected} triangle matching $c(n{K}_3)$ which is any connected graph containing $n$ vertex disjoint triangles. We obtain that $R(c(n{K}_3),c(n{K}_3))=7n-2$, somewhat larger than in the classical result of Burr, Erd\H os and Spencer for a triangle matching, $R(n{K}_3,n{K}_3)=5n$. The motivation is to determine the Ramsey number $R(C_n^2,C_n^2)$ of the square of a cycle $C_n^2$. We apply our Ramsey result for connected triangle matchings to show that the Ramsey number of an "almost" square of a cycle $C_n^{2,c}$ (a cycle of length $n$ in which all but at most a constant number $c$ of short diagonals are present) is asymptotic to $7n/3$.

Journal of Graph Theory, 2015

References in corpus (1)

• Partitioning 2-edge-colored graphs by monochromatic paths and cycles