Rainbow Turán numbers for short brooms

Abstract

A graph $G$ is rainbow-$F$-free if it admits a proper edge-coloring without a rainbow copy of $F$. The rainbow Turán number of $F$, denoted $\mathrm{e}{\mathrm{x}}^{\ast }(n,F)$, is the maximum number of edges in a rainbow-$F$-free graph on $n$ vertices. We determine bounds on the rainbow Turán numbers of stars with a single edge subdivided twice; we call such a tree with $t$ total edges a $t$-edge \textit{broom} with length-$3$ handle, denoted by $B_{t,3}$. We improve the best known upper bounds on $\mathrm{e}{\mathrm{x}}^{\ast }(n,B_{t,3})$ in all cases where $t\ne 2^s-2$. Moreover, in the case where $t$ is odd and in a few cases when $t\equiv 0\mathrm{mod}4$, we provide constructions asymptotically achieving these upper bounds. Our results also demonstrate a dependence of $\mathrm{e}{\mathrm{x}}^{\ast }(n,B_{t,3})$ on divisibility properties of $t$.

23 pages, 14 figures