We study the Lovasz number v along with two further SDP relaxations v 1/2 , v 2  of the independence number and the corresponding relaxations v, v 1/2 , v 2  of the chromatic number on random graphs G n,p . We prove that v, v 1/2 , v 2 (G n,p ) in the case p < n -1/2-e  are concentrated in intervals of constant length. Moreover, we estimate the probable value of v, v(G n,p ) etc. for essentially the entire range of edge probabilities p. As applications, we give improved algorithms for approximating α(G n,p ) and for deciding k-colorability in polynomial expected time.
['Amin Coja-Oghlan']
The Lovász Number of Random Graphs.