Colored Saturation Parameters for Rainbow Subgraphs. Issue 4 (8th March 2017)

• Record Type: Journal Article
• Authors: Barrus, Michael D.; Ferrara, Michael; Vandenbussche, Jennifer; Wenger, Paul S.
• Is Part Of: Journal of graph theory. Volume 86:Issue 4(2017)
• Page Start: 375
• Page End: 386
• Publication Date: 2017-03-08
• Subjects: saturation -- edge‐coloring -- rainbow; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22132
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: 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 R ( F ) denote the set of rainbow‐colored copies of F . A t ‐edge‐colored graph G is ( R ( F ), t ) ‐saturated if G does not contain a rainbow copy of F but for any edge e ∈ E ( G ¯ ) and any color i ∈ [ t ], the addition of e to G in color i creates a rainbow copy of F . Let sat t ( n, R ( F ) ) denote the minimum number of edges in an ( R ( F ), t ) ‐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 K n lies between n log n / log log n and n log n, 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.