2022/10/07 by Anastasia Halfpap, Halfpap, Anastasia · 2 citations
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.2210.03376
An edge-colored graph F is rainbow if each edge of F has a unique color. The rainbow Turán number ex^*(n,F) of a graph F is the maximum possible number of edges in a properly edge-colored n-vertex graph with no rainbow copy of F. The study of rainbow Turán numbers was introduced by Keevash, Mubayi, Sudakov, and Verstraëte in 2007. In this paper we focus on ex^*(n,P5). While several recent papers have investigated rainbow Turán numbers for ℓ-edge paths Pℓ, exact results have only been obtained for ℓ < 5, and P5 represents one of the smallest cases left open in rainbow Turán theory. In this paper, we prove that ex^*(n,P5) ≤ (5n)/(2). Combined with a lower-bound construction due to Johnston and Rombach, this result shows that ex^*(n,P5) = (5n)/(2) when n is divisible by 16, thereby settling the question asymptotically for all n. In addition, this result strengthens the conjecture that ex^*(n,Pℓ) = (ℓ)/(2)n + O(1) for all ℓ ≥ 3.