%P 1239-1249
%D 2024
%T The Rainbow Saturation Number Is Linear
%V 38
%A Natalie Behague
%A Tom Johnston
%A Shoham Letzter
%A Natasha Morrison
%A Shannon Ogden
%N 2
%X Given a graphH, we say that an edge-colored graphGisH-rainbow saturated ifit  does  not  contain  a  rainbow  copy  ofH,  but  the  addition  of  any  nonedge  in  any  color  creates  arainbow  copy  ofH.   The  rainbow  saturation  number  rsat(n,H)  is  the  minimum  number  of  edgesamong allH-rainbow saturated edge-colored graphs onnvertices.  We prove that for any nonemptygraphH, the rainbow saturation number is linear inn, thus proving a conjecture of Gir\~ao, Lewis,and Popielarz.  In addition, we give an improved upper bound on the rainbow saturation number ofthe complete graph, disproving a second conjecture of Gir\~ao, Lewis, and Popielarz.
%O This version is the version of record. For information on re-use, please refer to the publisher’s terms and conditions.
%I Society for Industrial and Applied Mathematics
%K edge-coloring, Mathematics, Mathematics, Applied, Physical Sciences, rainbow, saturation, Science & Technology
%J SIAM Journal on Discrete Mathematics
%L discovery10192107