Behague, Natalie
ORCID: 0000-0001-6616-1606, Johnston, Tom
ORCID: 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:
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