Rainbow saturation of graphs

Abstract

In this paper we study the following problem proposed by Barrus, Ferrara, Vandenbussche, and Wenger. Given a graph $H$ and an integer $t$, what is ${\mathrm{sat}}_t\left(n,\mathfrak{R}(H)\right)$, the minimum number of edges in a $t$-edge-coloured graph $G$ on $n$ vertices such that $G$ does not contain a rainbow copy of $H$, but adding to $G$ a new edge in any colour from $\{1,2,\dots ,t\}$ creates a rainbow copy of $H$? Here, we completely characterize the growth rates of ${\mathrm{sat}}_t\left(n,\mathfrak{R}(H)\right)$ as a function of $n$, for any graph $H$ belonging to a large class of connected graphs and for any $t\ge e(H)$. This classification includes all connected graphs of minimum degree $2$. In particular, we prove that ${\mathrm{sat}}_t\left(n,\mathfrak{R}(K_r)\right)=\hat{I}˜(n\log n)$, for any $r\ge 3$ and $t\ge \left(\genfrac{}{}{0ex}{}{r}{2}\right)$, thus resolving a conjecture of Barrus, Ferrara, Vandenbussche, and Wenger. We also pose several new problems and conjectures.

20 pages