Gallai-Ramsey numbers for rainbow paths

Abstract

Given graphs $G$ and $H$ and a positive integer $k$, the \emph{Gallai-Ramsey number}, denoted by $g{r}_k(G:H)$ is defined to be the minimum integer $n$ such that every coloring of $K_n$ using at most $k$ colors will contain either a rainbow copy of $G$ or a monochromatic copy of $H$. We consider this question in the cases where $G\in \{P_4,P_5\}$. In the case where $G=P_4$, we completely solve the Gallai-Ramsey question by reducing to the $2$-color Ramsey numbers. In the case where $G=P_5$, we conjecture that the problem reduces to the $3$-color Ramsey numbers and provide several results in support of this conjecture.

20 pages, 2 figures