Bounds for Gallai-Ramsey functions and numbers

Abstract

For two graphs $G,H$ and a positive integer $k$, the \emph{Gallai-Ramsey number} ${\mathrm{gr}}_k(G,H)$ is defined as the minimum number of vertices $n$ such that any $k$-edge-coloring of $K_n$ contains either a rainbow (all different colored) copy of $G$ or a monochromatic copy of $H$. If $G$ and $H$ are both complete graphs, then we call it Gallai-Ramsey function. Fox and Sudakov proved ${\mathrm{gr}}_k(K_s,K_t)\le s^{4kt}$. Alon et al. showed that ${\mathrm{gr}}_k(K_s,K_t)\le (2s^3+4s^2{)}^{kt}$. In this paper, we prove that ${\mathrm{gr}}_k(K_s,K_t)\le 2^{kt}{s}^{3kt}$ for $t\ge 47$. We also give better upper bounds for ${\mathrm{gr}}_k(G,H)$ when $G,H$ are some special graphs. In this paper, we derive some lower bounds for Gallai-Ramsey functions and numbers by Lovász Local Lemma.

17 pages