TY  - JOUR
EP  - 1249
IS  - 2
AV  - public
TI  - The Rainbow Saturation Number Is Linear
SN  - 0895-4801
KW  - edge-coloring
KW  -  Mathematics
KW  -  Mathematics
KW  -  Applied
KW  -  Physical Sciences
KW  -  rainbow
KW  -  saturation
KW  -  Science & Technology
N1  - This version is the version of record. For information on re-use, please refer to the publisher?s terms and conditions.
UR  - http://dx.doi.org/10.1137/23m1566881
ID  - discovery10192107
N2  - 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.
Y1  - 2024/06//
A1  - Behague, Natalie
A1  - Johnston, Tom
A1  - Letzter, Shoham
A1  - Morrison, Natasha
A1  - Ogden, Shannon
JF  - SIAM Journal on Discrete Mathematics
PB  - Society for Industrial and Applied Mathematics
SP  - 1239
VL  - 38
ER  -