Star-Critical Gallai-Ramsey Numbers of Graphs

The Gallai-Ramsey number gr(k) (K-3 : H-1, H-2,..., 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 is an element of [k]. We define the star-critical Gallai-Ramsey number gr(k)*(K-3 : H-1, H-2,..., H-k) as the smallest integer s such that every k-edge-colored K-n-K-1,K-n-1-s contains either a rainbow K-3 or a monochromatic H-i in color i for some i is an element of [k]. When H = H-l =...= H-k, we simply denote gr(k)* (K-3 : H-1, H-2,..., 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.