Asymptotic lower bounds for Gallai-Ramsey functions and numbers

Zhao Wang, Yaping Mao, Hengzhe Li, Suping Cui

Published 2020-07-08Version 1

For two graphs $G,H$ and a positive integer $k$, the \emph{Gallai-Ramsey number} ${\rm 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 \emph{Gallai-Ramsey function} ${\rm GR}_k(s,t)$, which is the minimum number of vertices $n$ such that any $k$-edge-coloring of $K_n$ contains either a rainbow copy of $K_s$ or a monochromatic copy of $K_t$. In this paper, we derive some lower bounds for Gallai-Ramsey functions and numbers by Lov\'{o}sz Local Lemma.