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.
Preview |
Text
Letzter_23m1566881.pdf Download (423kB) | Preview |
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.
| Type: | Article |
|---|---|
| Title: | The Rainbow Saturation Number Is Linear |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1137/23M1566881 |
| Publisher version: | http://dx.doi.org/10.1137/23m1566881 |
| Language: | English |
| Additional information: | This version is the version of record. For information on re-use, please refer to the publisher’s terms and conditions. |
| Keywords: | edge-coloring, Mathematics, Mathematics, Applied, Physical Sciences, rainbow, saturation, Science & Technology |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10192107 |
Archive Staff Only
 |
View Item |
