Constrained Ramsey Numbers of Matchings

Abstract

The rainbow Ramsey number $RR(G_1,G_2)$ or constrained Ramsey number $f(G_1,G_2)$ of two graphs $G_1$ and $G_2$ is defined to be the minimum integer $N$ such that any edge-coloring of the complete graph $K_N$ with any number of colors must contain either a subgraph isomorphic to $G_1$ with every edge the same color or a subgraph isomorphic to $G_2$ with every edge a different color. This number exists if and only if $G_1$ is a star or $G_2$ is acyclic. In this paper, we present the conjecture that the constrained Ramsey number of $n{K}_2$ and $m{K}_2$ is $m(n-1)+2$, along with a proof in the case $m\le \frac{3}{2}(n-1)$.