  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.
