Anti-Ramsey number of edge-disjoint rainbow spanning trees

Abstract

An edge-colored graph $G$ is called rainbow if every edge of $G$ receives a different color. The anti-Ramsey number of $t$ edge-disjoint rainbow spanning trees, denoted by $r(n,t)$, is defined as the maximum number of colors in an edge-coloring of $K_n$ containing no $t$ edge-disjoint rainbow spanning trees. Jahanbekam and West [J. Graph Theory, 2014] conjectured that for any fixed $t$, $r(n,t)=\left(\genfrac{}{}{0ex}{}{n-2}{2}\right)+t$ whenever $n\ge 2t+2\ge 6$. In this paper, we prove this conjecture. We also determine $r(n,t)$ when $n=2t+1$. Together with previous results, this gives the anti-Ramsey number of $t$ edge-disjoint rainbow spanning trees for all values of $n$ and $t$.

arXiv comment17 pages, fixed an error in the proof of Theorem 3 using Matroid methods