Abstract. Given a graph [Formula: see text], we say that an edge-colored graph [Formula: see text] is [Formula: see text]-rainbow saturated if it does not contain a rainbow copy of [Formula: see text], but the addition of any nonedge in any color creates a rainbow copy of [Formula: see text]. The rainbow saturation number [Formula: see text] is the minimum number of edges among all [Formula: see text]-rainbow saturated edge-colored graphs on [Formula: see text] vertices. We prove that for any nonempty graph [Formula: see text], the rainbow saturation number is linear in [Formula: see text], 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.

Abstract. A graph [Formula: see text] is common if the limit as [Formula: see text] of the minimum density of monochromatic labeled copies of [Formula: see text] in an edge coloring of [Formula: see text] with red and blue is attained by a sequence of quasirandom colorings. We apply an information-theoretic approach to show that certain graphs obtained from odd cycles and paths via gluing operations are common. In fact, for every pair [Formula: see text] of such graphs, there exists [Formula: see text] such that an appropriate linear combination of red copies of [Formula: see text] and blue copies of [Formula: see text] is minimized by a quasirandom coloring in which [Formula: see text] edges are red; such a pair [Formula: see text] is said to be [Formula: see text] -common. Our approach exploits a strengthening of the common graph property for odd cycles that was recently proved using Schur convexity. We also exhibit a [Formula: see text]-common pair [Formula: see text] such that [Formula: see text] is uncommon.