Rainbow Connection for Complete Multipartite Graphs

A path in an edge-colored graph is said to be rainbow if no color repeats on it. An edge-colored graph is said to be rainbow $k$-connected if every pair of vertices is connected by $k$ internally disjoint rainbow paths. The rainbow $k$-connection number ${\mathrm{r}\mathrm{c}}_k(G)$ is the minimum number of colors $\mathrm{\ell }$ such that there exists a coloring with $\mathrm{\ell }$ colors that makes $G$ rainbow $k$-connected. Let $f(k,t)$ be the minimum integer such that every $t$-partite graph with part sizes at least $f(k,t)$ has ${\mathrm{r}\mathrm{c}}_k(G)\le 4$ if $t=2$ and ${\mathrm{r}\mathrm{c}}_k(G)\le 3$ if $t\ge 3$. Answering a question of Fujita, Liu and Magnant, we show that $$f(k,t)=\lceil \frac{2k}{t-1}\rceil$$ for all $k\ge 2$, $t\ge 2$. We also give some conditions for which ${\mathrm{r}\mathrm{c}}_k(G)\le 3$ if $t=2$ and ${\mathrm{r}\mathrm{c}}_k(G)\le 2$ if $t\ge 3$.