Abstract

The saturation number of a graph is a famous and well-studied counterpoint to the Turán number, and the rainbow saturation number is a generalisation of the saturation number to the setting of coloured graphs. Specifically, for a given graph F, an edge-coloured graph is F-rainbow saturated if it does not contain a rainbow copy of F, but the addition of any non-edge in any colour creates a rainbow copy of F. The rainbow saturation number of F is the minimum number of edges in an F-rainbow saturated graph on n vertices. Girão, Lewis, and Popielarz conjectured that, like the saturation number, for all F the rainbow saturation number is linear in n. I will present our attractive and elementary proof of this conjecture, and finish with a discussion of related results and open questions.

This is joint work with Tom Johnston, Shoham Letzter, Natasha Morrison and Shannon Ogden.