Gallai-Ramsey Multiplicity

Abstract

Given two graphs $G$ and $H$, the \emph{general $k$-colored Gallai-Ramsey number} ${\mathrm{gr}}_k(G:H)$ is defined to be the minimum integer $m$ such that every $k$-coloring of the complete graph on $m$ vertices contains either a rainbow copy of $G$ or a monochromatic copy of $H$. Interesting problems arise when one asks how many such rainbow copy of $G$ and monochromatic copy of $H$ must occur. The \emph{Gallai-Ramsey multiplicity} ${\mathrm{GM}}_k(G,H)$ is defined as the minimum total number of rainbow copy of $G$ and monochromatic copy of $H$ in any exact $k$-coloring of $K_{{\mathrm{gr}}_k(G,H)}$. In this paper, we give upper and lower bounds for Gallai-Ramsey multiplicity involving some small rainbow subgraphs.

17 pages