= Chromatic number of the half-density binomial random graph
{title2=$\chi(G(n,1/2))\sim\frac n{2\log_2n}$}
For the <binomial random graph> $G(n,1/2)$, the <chromatic number> is $(1+o(1))n/(2\log_2n)$ <with high probability>. A <first moment method> bounds the <independence number> above. <Edge-disjoint clique packing> in the <complement graph>, followed by an <edge-exposure martingale> and a <union bound> over moderately large <vertex> sets, supplies <independent sets> for <greedy colouring by removing independent sets>.
Back to article page
