The Rainbow Saturation Number Is Linear

Natalie Behague, Tom Johnston, Shoham Letzter, Natasha Morrison, Shannon Ogden

Research output: Contribution to journalArticle (Academic Journal)peer-review

1 Citation (Scopus)

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ão, 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ão, Lewis, and Popielarz.
Original languageEnglish
Pages (from-to)1239-1249
Number of pages11
JournalSIAM Journal on Discrete Mathematics
Volume38
Issue number2
Early online date8 Apr 2024
DOIs
Publication statusPublished - 1 Jun 2024

Bibliographical note

Publisher Copyright:
© 2024 Society for Industrial and Applied Mathematics Publications. All rights reserved.

Fingerprint

Dive into the research topics of 'The Rainbow Saturation Number Is Linear'. Together they form a unique fingerprint.

Cite this