Rainbow Turán Problems for Paths and Forests of Stars
Rainbow Turán Problems for Paths and Forests of Stars
复制标题
星光路径和森林的彩虹图兰问题
DOI：
10.37236/6430
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Amites Sarkar
中科院分区：
文献类型：
--
作者：
Daniel R. Johnston;C. Palmer;Amites Sarkar
对于一个固定的图F，我们想确定一个在n个顶点上的正确边着色的图中的最大边数，该图不包含F的彩虹拷贝，也就是说，F的一个拷贝的所有边都接收不同的颜色。这个最大值，记为$ex^*（n，F）$，是F$的{\displaystyle {\mathrine Tur\'an number}，它的系统研究是由Keevash，Mubayi，Sudakov和Verstra\“埃特在2007年发起的。当$F$是星森林时，我们精确地确定$ex^*（n，F）$，并且当$F$是具有$k$条边的路径时，给出$ex^*（n，F）$的界，从而反驳了Keevash等人的猜想。
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.