Natasha Morrison, University of Victoria
Authors: Joint work with Natalie Behague (University of Victoria), Tom Johnston, (University of Bristol) Shannon Ogden (University of Victoria), and Shoham Letzter (University College London)
2023 AWM Research Symposium
Extremal and Probabilistic Combinatorics [Organized by Jinyoung Park and Corrine Yap]
Given a graph H, we say that 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 rsat(n, H) is the minimum number of edges among all H-rainbow saturated edge-coloured graphs on n vertices. We prove 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.