Anti-Ramsey number of edge-disjoint rainbow spanning trees

Series
Graph Theory Seminar
Time
Thursday, April 9, 2020 - 2:00pm for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Zhiyu Wang – University of South Carolina
Organizer
Xingxing Yu

An edge-colored graph $G$ is called \textit{rainbow} if every edge of $G$ receives a different color. The \textit{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 [{\em J. Graph Theory, 2016}] conjectured that for any fixed $t$, $r(n,t)=\binom{n-2}{2}+t$ whenever $n\geq 2t+2 \geq 6$. We show their conjecture is true and 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$. Joint work with Linyuan Lu.