Rainbow Turán numbers for paths of length four

Abstract

Given a set $V$ of $n$ vertices and an integer $k\ge 1$, our goal is to maximize the number of edges in graphs $G_1,G_2,\dots ,G_k$, defined on $V$, under the constraint that the union of all graphs, thought of as a multi-graph, does not contain a rainbow copy of the path $P_5$ on $5$ vertices, that is, a copy of $P_5$ with each of its four edges belonging to a different $G_i$. We consider two versions of the problem, in which, respectively, ${\sum }_{i}e(G_i)$ and ${\min }_{i}e(G_i)$ is maximized. In the former case, we determine the maximum precisely for all $k\le n-1$ (and also for $P_4$). In the latter, we obtain an asymptotic value for $k\in \{5,6,9\}$ and formulate a very plausible conjecture for all other values of $k$. We also solve the problem for $k=4$, but under an additional assumption of completeness.