We consider the MAX k-CUT problem in random graphs G _n,p. First, we estimate the probable weight of a MAX k-CUT using probabilistic counting arguments and by analyzing a simple greedy heuristic. Then, we give an algorithm that approximates MAX k-CUT within expected polynomial time. The approximation ratio tends to 1 as np→ ∞. As an application, we obtain an algorithm for approximating the chromatic number of G _n,p, 1/n≤ p ≤ 1/2, within a factor of in polynomial expected time, thereby answering a question of Krivelevich and Vu, and extending a result of Coja-Oghlan and Taraz. We give similar algorithms for random regular graphs G _n,r.