Chromatic number of a binomial random graph ($\mathbb{E}\chi (G(n,p))\sim n/(2{\log }_{1/(1-p)}n)$)

For a fixed probability strictly between zero and one, the largest independent set has leading size $2{\log }_{1/(1-p)}n$, giving a lower bound for colouring. The matching upper bound uses independent sets in every large subset of a dense random graph, then repeatedly colours and removes such sets. A sufficiently strong probability estimate makes the failure contribution negligible for the expectation.

For fixed $p$ and $\gamma >0$, Janson inequality bounds the failure probability for a given large vertex subset by $\exp (-c|U{|}^2/(\log n{)}^4)$. A union bound over all at most $2^n$ subsets still tends to zero. This uniform statement is essential because vertex sets left by a greedy colouring procedure depend on the graph; one cannot assume each adaptively chosen remainder is an independent fresh random graph.