The Gallai-Ramsey number $gr_{ 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 $gr_{ k}^{ *}(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 $gr_{ k}^{ *}(K_{ 3}: H_{ 1}, H_{ 2}, \cdots, H_{ k})$ by $gr_{ k}^{ *}(K_{ 3}: H)$. We determine the star-critical Gallai-Ramsey numbers for complete graphs and some small graphs. Furthermore, we show that $gr_{ k}^{ *}(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.
Categories: math.CO