Rödl and Ruciński studied this problem for the random graph G_n,p in the symmetric case when k is fixed and F₁=...=F_k=F. They proved that such a coloring exists asymptotically almost surely (a.a.s.) provided that p ≤bn^–β for some constants b=b(F,k) and β=β(F). Their proof was, however, non-constructive. This result is essentially best possible because for p ≥Bn^–β, where B=B(F, k) is a large constant, such an edge-coloring does not exist. For this reason we refer to n^–β as a threshold function.

In this paper we address the case when F₁,..., F_k are cliques of different sizes and propose an algorithm that a.a.s. finds a valid k-edge-coloring of G_n,p with p ≤bn^–β for some constants b=b(F₁,..., F_k, k) and β=β(F₁,..., F_k). Kohayakawa and Kreuter conjectured that is a threshold function in this case. This algorithm can be also adjusted to produce a valid k-coloring in the symmetric case.