Star-critical Gallai-Ramsey numbers of graphs

Abstract

The Gallai-Ramsey number $g{r}_k(K_3:H_1,H_2,\cdots ,H_k)$ is the smallest integer $n$ such that every $k$-edge-colored $K_n$ contains either a rainbow $K_3$ or a monochromatic $H_i$ in color $i$ for some $i\in [k]$. We find the largest star that can be removed from $K_n$ such that the underlying graph is still forced to have a rainbow $K_3$ or a monochromatic $H_i$ in color $i$ for some $i\in [k]$. Thus, we define the star-critical Gallai-Ramsey number $g{r}_k^{\ast }(K_3:H_1,H_2,\cdots ,H_k)$ as the smallest integer $s$ such that every $k$-edge-colored $K_n-K_{1,n-1-s}$ contains either a rainbow $K_3$ or a monochromatic $H_i$ in color $i$ for some $i\in [k]$. When $H=H_1=\cdots =H_k$, we simply denote $g{r}_k^{\ast }(K_3:H_1,H_2,\cdots ,H_k)$ by $g{r}_k^{\ast }(K_3:H)$. We determine the star-critical Gallai-Ramsey numbers for complete graphs and some small graphs. Furthermore, we show that $g{r}_k^{\ast }(K_3:H)$ is exponential in $k$ if $H$ is not bipartite, linear in $k$ if $H$ is bipartite but not a star and constant (not depending on $k$) if $H$ is a star.

19 pages, 1 figure