On the k-orientability of random graphs

Let G(n, m) be an undirected random graph with n vertices and m multiedges that may include loops, where each edge is realized by choosing its two vertices independently and uniformly at random with replacement from the set of all n vertices. The random graph G(n, m) is said to be k-orientable, where k >= 2 is an integer, if there exists an orientation of the edges such that the maximum out-degree is at most k. Let c(k) = sup {c : G(n, cn) is k-orientable w.h.p.}. We prove that for k large enough, 1 - 2(k) exp (-k + 1 + e(-k/4)) < c(k)/k < 1 - exp (-2k (1 - e(-2k))), and the time c(k)n is a threshold for the emergence of a giant subgraph of size (-)(n) whose edges are more than k times its vertices. Other results are presented. (C) 2008 Elsevier B.V. All rights reserved.