Colored Saturation Parameters for Bipartite Graph

Let F and H be fixed graphs and let G be a spanning subgraph of H. G is an F-free subgraph of H if F is not a subgraph of G. We say that G is an F-saturated subgraph of H if G is F-free and for any edge e 2 E(H) .. E(G), F is a subgraph of G + e. The saturation number of F in Kn,n, denoted sat(Kn,n, F), is the minimum size of an F-saturated subgraph of Kn,n. A t-edge-coloring of a graph G is a labeling f : E(G) ! [t], where [t] denotes the set f1, 2, . . . , tg. The labels assigned to the edges are called colors. A rainbow coloring is a coloring in which all edges have distinct colors. Given a family F of edge-colored graphs, a t-edge-colored graph H is (F, t)-saturated if H contains no member of F but the addition of any edge in any color completes a member of F. In this thesis we study the minimum size of (F, t)-saturated subgraphs of edge-colored complete bipartite graphs. Specifically we provide bounds on the minimum size of these subgraphs for a variety of families of edge-colored bipartite graphs, including monochromatic matchings, rainbow matchings, and rainbow stars.