On the proper rainbow saturation numbers of cliques, paths, and odd cycles

Abstract

Given a graph $H$, we say a graph $G$ is properly rainbow $H$-saturated if there is a proper edge-coloring of $G$ which contains no rainbow copy of $H$, but adding any edge to $G$ makes such an edge-coloring impossible. The proper rainbow saturation number, denoted ${\text{sat}}^{\ast }(n,H)$, is the minimum number of edges in an $n$-vertex rainbow $H$-saturated graph. We determine the proper rainbow saturation number for paths up to an additive constant and asymptotically determine ${\text{sat}}^{\ast }(n,K_4)$. In addition, we bound ${\text{sat}}^{\ast }(n,H)$ when $H$ is a larger clique, tree of diameter at least 4, or odd cycle.