MAX k-CUT and Approximating the Chromatic Number of Random Graphs

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 $$ O\left( {\sqrt {np} } \right) $$ 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.