DMS Discrete Mathematics

Shannon Ogden (Victoria U)

Title: The Rainbow Saturation Number is Linear

Abstract: An edge-coloured graph is said to be rainbow if every edge in the graph has a distinct colour. Given a graph H, an edge-coloured graph G is H-rainbow saturated if it does not contain a rainbow copy of H, but the addition of any non-edge, in any colour, creates a rainbow copy of H. The rainbow saturation number, denote by rsat(n,H), is the minimum number of edges in an H-rainbow saturated edge-coloured graph on n vertices. In this talk, we will show that, for any non-empty graph H, the rainbow saturation number is linear in n, thus proving a conjecture of Girão, Lewis, and Popielarz. Based on work with Natalie Behague, Tom Johnston, Shoham Letzter, and Natasha Morrison.