TY - JOUR
T1 - Rainbow Turán problems for paths and forests of stars
AU - Johnston, Daniel
AU - Palmer, Cory
AU - Sarkar, Amites
N1 - Publisher Copyright:
© 2017, Australian National University. All rights reserved.
PY - 2017/2/17
Y1 - 2017/2/17
N2 - 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.
AB - 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.
KW - Paths
KW - Rainbow Turán numbers
KW - Stars
UR - http://www.scopus.com/inward/record.url?scp=85013379954&partnerID=8YFLogxK
U2 - 10.37236/6430
DO - 10.37236/6430
M3 - Article
AN - SCOPUS:85013379954
SN - 1077-8926
VL - 24
JO - Electronic Journal of Combinatorics
JF - Electronic Journal of Combinatorics
IS - 1
M1 - #P1.34
ER -