A note on rainbow saturation number of paths

Abstract

For a fixed graph $F$ and an integer $t$, the \dfn{rainbow saturation number} of $F$, denoted by $sa{t}_t(n,\mathfrak{R}(F))$, is defined as the minimum number of edges in a $t$-edge-colored graph on $n$ vertices which does not contain a \dfn{rainbow copy} of $F$, i.e., a copy of $F$ all of whose edges receive a different color, but the addition of any missing edge in any color from $[t]$ creates such a rainbow copy. Barrus, Ferrara, Vardenbussche and Wenger prove that $sa{t}_t(n,\mathfrak{R}(P_{\ell }))\ge n-1$ for $\ell \ge 4$ and $sa{t}_t(n,\mathfrak{R}(P_{\ell }))\le \lceil \frac{n}{\ell -1}\rceil \cdot \left(\genfrac{}{}{0ex}{}{\ell -1}{2}\right)$ for $t\ge \left(\genfrac{}{}{0ex}{}{\ell -1}{2}\right)$, where $P_{\ell }$ is a path with $\ell$ edges. In this short note, we improve the upper bounds and show that $sa{t}_t(n,\mathfrak{R}(P_{\ell }))\le \lceil \frac{n}{\ell }\rceil \cdot \left(\left(\genfrac{}{}{0ex}{}{\ell -2}{2}\right)+4\right)$ for $\ell \ge 5$ and $t\ge 2\ell -5$.

9 pages