Rainbow Turán problems for paths and forests of stars (Q510352): Difference between revisions

Summary: 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 \(\mathrm{ex}^\ast(n,F)\), is the rainbow Turán number of \(F\), and its systematic study was initiated by \textit{P. Keevash} et al. [Comb. Probab. Comput. 16, No. 1, 109--126 (2007; Zbl 1119.05058)]. We determine \(\mathrm{ex}^\ast(n,F)\) exactly when \(F\) is a forest of stars, and give bounds on \(\mathrm{ex}^\ast(n,F)\) when \(F\) is a path with \(l\) edges, disproving a conjecture in the aforementioned paper for \(l=4\).