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$.
@article{10_37236_6430,
author = {Daniel Johnston and Cory Palmer and Amites Sarkar},
title = {Rainbow {Tur\'an} problems for paths and forests of stars},
journal = {The electronic journal of combinatorics},
year = {2017},
volume = {24},
number = {1},
doi = {10.37236/6430},
zbl = {1355.05111},
url = {http://geodesic.mathdoc.fr/articles/10.37236/6430/}
}
TY - JOUR
AU - Daniel Johnston
AU - Cory Palmer
AU - Amites Sarkar
TI - Rainbow Turán problems for paths and forests of stars
JO - The electronic journal of combinatorics
PY - 2017
VL - 24
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/6430/
DO - 10.37236/6430
ID - 10_37236_6430
ER -
%0 Journal Article
%A Daniel Johnston
%A Cory Palmer
%A Amites Sarkar
%T Rainbow Turán problems for paths and forests of stars
%J The electronic journal of combinatorics
%D 2017
%V 24
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/6430/
%R 10.37236/6430
%F 10_37236_6430
Daniel Johnston; Cory Palmer; Amites Sarkar. Rainbow Turán problems for paths and forests of stars. The electronic journal of combinatorics, Tome 24 (2017) no. 1. doi: 10.37236/6430
