Ramsey and Gallai-Ramsey numbers for stars with extra independent edges

摘要

Given a graph G and a positive integer k, define the Gallai-Ramsey number to be the minimum number of vertices n such that any k-edge coloring of K-n contains either a rainbow (all different colored) triangle or a monochromatic copy of G. In this paper, we obtain general upper and lower bounds on the Gallai-Ramsey numbers for the graph G = S-t(r) obtained from a star of order t by including r extra independent edges between leaves of the star so there are r triangles and t - 2r - 1 pendant edges in S-t(r). We also prove some sharp results when r = 2. (C) 2020 Elsevier B.V. All rights reserved.