eprintid: 10192107
rev_number: 9
eprint_status: archive
userid: 699
dir: disk0/10/19/21/07
datestamp: 2024-05-14 11:05:43
lastmod: 2024-05-14 11:05:43
status_changed: 2024-05-14 11:05:43
type: article
metadata_visibility: show
sword_depositor: 699
creators_name: Behague, Natalie
creators_name: Johnston, Tom
creators_name: Letzter, Shoham
creators_name: Morrison, Natasha
creators_name: Ogden, Shannon
title: The Rainbow Saturation Number Is Linear
ispublished: pub
divisions: UCL
divisions: B04
divisions: C06
divisions: F59
keywords: edge-coloring, Mathematics, Mathematics, Applied, Physical Sciences, rainbow, saturation, Science & Technology
note: This version is the version of record. For information on re-use, please refer to the publisher’s terms and conditions.
abstract: 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.
date: 2024-06
date_type: published
publisher: Society for Industrial and Applied Mathematics
official_url: http://dx.doi.org/10.1137/23m1566881
oa_status: green
full_text_type: pub
language: eng
primo: open
primo_central: open_green
verified: verified_manual
elements_id: 2271967
doi: 10.1137/23M1566881
lyricists_name: Letzter, Shoham
lyricists_id: SLETZ34
actors_name: Letzter, Shoham
actors_id: SLETZ34
actors_role: owner
funding_acknowledgements: [PIMS postdoctoral fellowship]; [Royal Society]; RGPIN-2021-02511 [NSERC]; DGECR-2021-00047 [NSERC Early Career Supplement]; [NSERC CGS M]
full_text_status: public
publication: SIAM Journal on Discrete Mathematics
volume: 38
number: 2
pagerange: 1239-1249
pages: 11
issn: 0895-4801
citation:        Behague, Natalie;    Johnston, Tom;    Letzter, Shoham;    Morrison, Natasha;    Ogden, Shannon;      (2024)    The Rainbow Saturation Number Is Linear.                   SIAM Journal on Discrete Mathematics , 38  (2)   pp. 1239-1249.    10.1137/23M1566881 <https://doi.org/10.1137/23M1566881>.       Green open access   
 
document_url: https://discovery.ucl.ac.uk/id/eprint/10192107/7/Letzter_23m1566881.pdf