PIMS-UVic Discrete Math Seminar: Andrew Lane

Given a graph H, say that a graph G is properly rainbow H-saturated if there exists a rainbow H-free proper edge-colouring of G and, for any non-edge e of G, every proper edge-colouring of G+e contains a rainbow copy of H. The proper rainbow saturation number is the minimum number of edges in a properly rainbow H-saturated graph on n vertices. This is a natural variant of the graph saturation problem based on the rainbow extremal number. In this talk, we will prove bounds on the proper rainbow saturation number for specific classes of graphs, and we will prove general bounds on the proper rainbow saturation number using related saturation numbers.

Joint work with Natasha Morrison.