Anti-Ramsey number of edge-disjoint rainbow spanning trees in all graphs

Abstract

An edge-colored graph $G$ is called \textit{rainbow} if every edge of $G$ receives a different color. Given any host graph $G$, the \textit{anti-Ramsey} number of $t$ edge-disjoint rainbow spanning trees in $G$, denoted by $r(G,t)$, is defined as the maximum number of colors in an edge-coloring of $G$ containing no $t$ edge-disjoint rainbow spanning trees. For any vertex partition $P$, let $E(P,G)$ be the set of non-crossing edges in $G$ with respect to $P$. In this paper, we determine $r(G,t)$ for all host graphs $G$: $r(G,t)=|E(G)|$ if there exists a partition $P_0$ with $|E(G)|-|E(P_0,G)|<t(|P_0|-1)$; and $r(G,t)={\max }_{P:|P|\ge 3}\{|E(P,G)|+t(|P|-2)\}$ otherwise. As a corollary, we determine $r(K_{p,q},t)$ for all values of $p,q,t$, improving a result of Jia, Lu and Zhang.

11 pages

References in corpus (2)

• Anti-Ramsey numbers of graphs with some decomposition family sequences
• Anti-Ramsey numbers for paths

Cited by in corpus (1)

• Anti-Ramsey numbers for trees in complete multi-partite graphs