The Rainbow Saturation Number Is Linear

This is the authors' abstract. We don't add key points for this paper.

.Given a graph \(H\), we say that an edge-colored graph \(G\) is \(H\)-rainbow saturated if it does not contain a rainbow copy of \(H\), but the addition of any nonedge in any color 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-colored graphs on \(n\) vertices. We prove that for any nonempty graph \(H\), the rainbow saturation number is linear in \(n\), thus proving a conjecture of Girão, Lewis, and Popielarz. In addition, we give an improved upper bound on the rainbow saturation number of the complete graph, disproving a second conjecture of Girão, Lewis, and Popielarz.Keywordssaturationrainbowedge-coloringMSC codes05C35