Colored Saturation Parameters for Rainbow Subgraphs

Inspired by a 1987 result of Hanson and Toft Edge‐colored saturated graphs, J Graph Theory 11 (1987), 191–196] and several recent results, we consider the following saturation problem for edge‐colored graphs. An edge‐coloring of a graph F is rainbow if every edge of F receives a different color. Let denote the set of rainbow‐colored copies of F. A t‐edge‐colored graph G is ‐saturated if G does not contain a rainbow copy of F but for any edge and any color , the addition of e to G in color i creates a rainbow copy of F. Let denote the minimum number of edges in an ‐saturated graph of order n. We call this the rainbow saturation number of F. In this article, we prove several results about rainbow saturation numbers of graphs. In stark contrast with the related problem for monochromatic subgraphs, wherein the saturation is always linear in n, we prove that rainbow saturation numbers have a variety of different orders of growth. For instance, the rainbow saturation number of the complete graph lies between and , the rainbow saturation number of an n‐vertex star is quadratic in n, and the rainbow saturation number of any tree that is not a star is at most linear.