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 ex∗ (n, F), is the rainbow Turán number of F, and its systematic study was initiated by Keevash, Mubayi, Sudakov and Verstraëte [Combinatorics, Probability and Computing 16 (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 l edges, disproving a conjecture in the aforementioned paper for l = 4.
The Electronic Journal of Combinatorics
Required Publisher's Statement
Authors retain the copyright of their articles.
Rainbow Turán problems for paths and forests of stars, (Daniel Johnston, Cory Palmer, Amites Sarkar). Elec. J. Combinatorics Vol 24 (1) no. P1.34, 2017