Gallai-Ramsey Numbers for $\ell$-Connected Graphs

Abstract

Given a nonempty graph $G$, a collection of nonempty graphs $\mathcal{H}$, and a positive integer $k$, the Gallai-Ramsey number ${\mathrm{gr}}_k(G:\mathcal{H})$ is defined to be the minimum positive integer $n$ such that every exact $k$-edge-coloring of a complete graph $K_n$ contains either a rainbow copy of $G$ or a monochromatic copy of some element in $\mathcal{H}$. In this paper, we obtain some exact values and general lower and upper bounds for ${\mathrm{gr}}_k(G:{\mathcal{F}}^{\ell })$, where ${\mathcal{F}}^{\ell }$ is the set of $\ell$-connected graphs and $G\in \{P_5,K_{1,3}\}$.

12 pages