Rainbow Turán problems for paths and forests of stars
Abstract
For a fixed graph $F$, we would like to determine the maximum number of edges in a properly edgecolored graph on $n$ vertices which does not contain a {\emph rainbow copy} of $F$, that is, a copy of $F$ all of whose edges receive a different color. This maximum, denoted by $ex^*(n,F)$, is the {\emph rainbow Turán number} of $F$, and its systematic study was initiated by Keevash, Mubayi, Sudakov and Verstraëte in 2007. We determine $ex^*(n,F)$ exactly when $F$ is a forest of stars, and give bounds on $ex^*(n,F)$ when $F$ is a path with $k$ edges, disproving a conjecture in Keevash et al.
 Publication:

arXiv eprints
 Pub Date:
 August 2016
 arXiv:
 arXiv:1609.00069
 Bibcode:
 2016arXiv160900069J
 Keywords:

 Mathematics  Combinatorics
 EPrint:
 Updated Theorem 11