%0 Journal Article
%@ 0895-4801
%A Behague, Natalie
%A Johnston, Tom
%A Letzter, Shoham
%A Morrison, Natasha
%A Ogden, Shannon
%D 2024
%F discovery:10192107
%I Society for Industrial and Applied Mathematics
%J SIAM Journal on Discrete Mathematics
%K edge-coloring, Mathematics, Mathematics, Applied, Physical Sciences, rainbow, saturation, Science & Technology
%N 2
%P 1239-1249
%T The Rainbow Saturation Number Is Linear
%U https://discovery.ucl.ac.uk/id/eprint/10192107/
%V 38
%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.
%Z This version is the version of record. For information on re-use, please refer to the publisher’s terms and conditions.