The rainbow Turán number of $P_5$

Abstract

An edge-colored graph $F$ is rainbow if each edge of $F$ has a unique color. The rainbow Turán number $e{x}^{\ast }(n,F)$ of a graph $F$ is the maximum possible number of edges in a properly edge-colored $n$-vertex graph with no rainbow copy of $F$. The study of rainbow Turán numbers was introduced by Keevash, Mubayi, Sudakov, and Verstraëte in 2007. In this paper we focus on $e{x}^{\ast }(n,P_5)$. While several recent papers have investigated rainbow Turán numbers for $\ell$-edge paths $P_{\ell }$, exact results have only been obtained for $\ell <5$, and $P_5$ represents one of the smallest cases left open in rainbow Turán theory. In this paper, we prove that $e{x}^{\ast }(n,P_5)\le \frac{5n}{2}$. Combined with a lower-bound construction due to Johnston and Rombach, this result shows that $e{x}^{\ast }(n,P_5)=\frac{5n}{2}$ when $n$ is divisible by $16$, thereby settling the question asymptotically for all $n$. In addition, this result strengthens the conjecture that $e{x}^{\ast }(n,P_{\ell })=\frac{\ell }{2}n+O(1)$ for all $\ell \ge 3$.