{
"id": "1901.03308",
"version": "v1",
"published": "2019-01-10T18:23:00.000Z",
"updated": "2019-01-10T18:23:00.000Z",
"title": "Lower bounds for rainbow Turán numbers of paths and other trees",
"authors": [
"Daniel Johnston",
"Puck Rombach"
],
"categories": [
"math.CO"
],
"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 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.",
"revisions": [
{
"version": "v1",
"updated": "2019-01-10T18:23:00.000Z"
}
],
"analyses": {
"subjects": [
"05C15",
"05C35",
"05C38"
],
"keywords": [
"rainbow turán numbers",
"lower bounds",
"maximum number",
"small diameter",
"similar bounds"
],
"note": {
"typesetting": "TeX",
"pages": 0,
"language": "en",
"license": "arXiv",
"status": "editable"
}
}
}