pith. sign in

arxiv: 1609.00069 · v2 · pith:SRDDJZ3Hnew · submitted 2016-08-31 · 🧮 math.CO

Rainbow Tur\'an problems for paths and forests of stars

classification 🧮 math.CO
keywords edgesrainbowcopydetermineemphgraphkeevashmaximum
0
0 comments X
read the original abstract

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 {\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\'an number} of $F$, and its systematic study was initiated by Keevash, Mubayi, Sudakov and Verstra\"ete 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.