Premium
Colored Saturation Parameters for Rainbow Subgraphs
Author(s) -
Barrus Michael D.,
Ferrara Michael,
Vandenbussche Jennifer,
Wenger Paul S.
Publication year - 2017
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22132
Subject(s) - rainbow , combinatorics , colored , mathematics , monochromatic color , saturation (graph theory) , discrete mathematics , vertex (graph theory) , graph , physics , optics , law , political science
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 . Letsat 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.