## arXiv Analytics

### arXiv:1901.03308 [math.CO]AbstractReferencesReviewsResources

#### Lower bounds for rainbow Turán numbers of paths and other trees

Published 2019-01-10Version 1

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\'{a}n number of $F$. We show that $ex^*(n,P_k)\geq \frac{k}{2}n + O(1)$ where $P_k$ is a path on $k\geq 3$ edges, generalizing a result by Maamoun and Meyniel and by Johnston, Palmer and Sarkar. We show similar bounds for brooms on $2^s-1$ edges and diameter $\leq 10$ and a few other caterpillars of small diameter.

Categories: math.CO
Subjects: 05C15, 05C35, 05C38
Related articles: Most relevant | Search more
arXiv:math/0410218 [math.CO] (Published 2004-10-08)
The sum of degrees in cliques
arXiv:1310.5882 [math.CO] (Published 2013-10-22)
Lower bounds on the maximum number of non-crossing acyclic graphs
arXiv:1006.3783 [math.CO] (Published 2010-06-18)
Crossings, colorings, and cliques