On rainbow-k-connectivity of random graphs

A path in an edge-colored graph is called a rainbow path   if the edges on it have distinct colors. For k⩾1k⩾1, the rainbow-k-connectivity of a graph G  , denoted by rck(G)rck(G), is the minimum number of colors required to color the edges of G in such a way that every two distinct vertices are connected by at least k internally vertex-disjoint rainbow paths. In this paper, we study rainbow-k  -connectivity in the setting of random graphs. We show that for every fixed integer d⩾2d⩾2 and every k⩽O(logn), p=(logn)1/d/n(d−1)/d is a sharp threshold function for the property rck(G(n,p))⩽drck(G(n,p))⩽d. This substantially generalizes a result in [Y. Caro, A. Lev, Y. Roditty, Z. Tuza, R. Yuster, On rainbow connection, Electron. J. Comb. 15 (2008)], stating that p=logn/n is a sharp threshold function for the property rc1(G(n,p))⩽2rc1(G(n,p))⩽2. As a by-product, we obtain a polynomial-time algorithm that makes G(n,p)G(n,p) rainbow-k  -connected using at most one more than the optimal number of colors with probability 1−o(1)1−o(1), for all k⩽O(logn) and p=n−ϵ(1±o(1))p=n−ϵ(1±o(1)) for any constant ϵ∈[0,1)ϵ∈[0,1).

► Give a sharp threshold function for G(n,p)G(n,p) having rainbow-k-connectivity d. ► Propose a randomize polynomial time algorithm that rainbow-k-colors random graphs using near-optimal number of colors. ► Our results hold for a large range of the parameters.