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 language | English |
---|---|
Pages (from-to) | 1239-1249 |
Number of pages | 11 |
Journal | SIAM Journal on Discrete Mathematics |
Volume | 38 |
Issue number | 2 |
Early online date | 8 Apr 2024 |
DOIs | |
Publication status | Published - 1 Jun 2024 |
Bibliographical note
Publisher Copyright:© 2024 Society for Industrial and Applied Mathematics Publications. All rights reserved.