The $(k,\ell )$-Rainbow Index for Complete Bipartite and Multipartite Graphs

Abstract

A tree in an edge-colored graph G is said to be a rainbow tree if no two edges on the tree share the same color. Given two positive integers k, $\ell$ with $k\ge 3$, the $(k,\ell )$-rainbow index $rx_{k,\ell }(G)$ of G is the minimum number of colors needed in an edge-coloring of G such that for any set S of k vertices of G, there exist $\ell$ internally disjoint rainbow trees connecting S. This concept was introduced by Chartrand et al. in 2010. It is very difficult to determine the $(k,\ell )$-rainbow index for a general graph. Chartrand et al. determined the (k, 1)-rainbow index of all unicyclic graphs and the $(3,\ell )$-rainbow index of complete graphs for $\ell =1,2$. We showed that for every pair of positive integers $k,\ell$ with $k\ge 3$, there exists a positive integer $N=N(k,\ell )$ such that $rx_{k,\ell }(K_{n})=k$ for every integer $n\ge N$, which settled down a conjecture of Chartrand et al. In this paper, we use probabilistic method and bipartite Ramsey numbers to obtain similar results of the $(k,\ell )$-rainbow index for complete bipartite graphs. For complete multipartite graphs, we get similar results for most cases, however, since there is no any result on the multipartite Ramsey numbers in general, we can only get a value that differs by 1 from the exact value for some cases.