Rainbow Connection for Complete Multipartite Graphs

Abstract

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{rc}}_k(G)$ is the minimum number of colors $\ell$ such that there exists a coloring with $\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{rc}}_k(G)\le 4$ if $t=2$ and ${\mathrm{rc}}_k(G)\le 3$ if $t\ge 3$. Answering a question of Fujita, Liu and Magnant, we show that \[ f(k,t) = \left\lceil \frac{2k}{t-1} \right\rceil \] for all $k\ge 2$, $t\ge 2$. We also give some conditions for which ${\mathrm{rc}}_k(G)\le 3$ if $t=2$ and ${\mathrm{rc}}_k(G)\le 2$ if $t\ge 3$.

10 pages, 4 figures