Login (DCU Staff Only)
Login (DCU Staff Only)

DORAS | DCU Research Repository

Explore open access research and scholarly works from DCU

Advanced Search

The Rainbow Saturation Number Is Linear

Behague, Natalie orcid logoORCID: 0000-0001-6616-1606, Johnston, Tom orcid logoORCID: 0000-0002-4119-4599, Letzter, Shoham, Morrison, Natasha and Ogden, Shannon (2024) The Rainbow Saturation Number Is Linear. SIAM Journal on Discrete Mathematics, 38 (2). pp. 1239-1249. ISSN 0895-4801

Abstract
Given a graph H, we say that an edge-coloured graph G is H-rainbow saturated if it does not contain a rainbow copy of H, but the addition of any non-edge in any colour creates a rainbow copy of H. The rainbow saturation number rsat(n, H) is the minimum number of edges among all H-rainbow saturated edge-coloured graphs on n vertices. We prove that for any non-empty graph H, the rainbow saturation number is linear in n, thus proving a conjecture of Gir˜ao, Lewis, and Popielarz. In addition, we also give an improved upper bound on the rainbow saturation number of the complete graph, disproving a second conjecture of Gir˜ao, Lewis, and Popielarz.
Metadata
Item Type:Article (Published)
Refereed:Yes
Uncontrolled Keywords:Combinatorics
Subjects:Mathematics
DCU Faculties and Centres:DCU Faculties and Schools > Faculty of Science and Health > School of Mathematical Sciences
Publisher:Society for Industrial and Applied Mathematics
Official URL:https://epubs.siam.org/doi/10.1137/23M1566881
Copyright Information:Authors
ID Code:33294
Deposited On:31 Aug 2026 14:02 by Natalie Behague . Last Modified 31 Aug 2026 14:02
Documents

Full text available as:

[thumbnail of 2211.08589v2.pdf]
Preview
PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Creative Commons: Attribution 4.0
192kB
Metrics

Altmetric Badge

Dimensions Badge

Downloads

Downloads

Downloads per month over past year

Archive Staff Only: edit this record