Lower bounds for rainbow Turán numbers of paths and other trees

Abstract

For a fixed graph $F$, we would like to determine the maximum number of edges in a properly edge-colored graph on $n$ vertices which does not contain a rainbow copy of $F$, that is, a copy of $F$ all of whose edges receive a different color. This maximum, denoted by $e{x}^{\ast }(n,F)$, is the rainbow Turán number of $F$. We show that $e{x}^{\ast }(n,P_k)\ge \frac{k}{2}n+O(1)$ where $P_k$ is a path on $k\ge 3$ edges, generalizing a result by Maamoun and Meyniel and by Johnston, Palmer and Sarkar. We show similar bounds for brooms on $2^s-1$ edges and diameter $\le 10$ and a few other caterpillars of small diameter.