The chromatic number of random graphs (Q5903892)

Let \(G_ p\) denote a random graph with vertex set \(\{\) 1,2,...,n\(\}\), in which the edges are chosen independently and with probability \(p=p(n)\), \(0<p<1\). The main aim of the paper is the study of the clique number \(cl(G_ p)\) and chromatic number \(\chi (G_ p)\) of \(G_ p\) for p constant. The notation and terminology used are standard. It is proved that for a fixed probability p, \(0<p<1\), almost every random graph \(G_{n,p}\) has chromatic number \[ (+o(1))\log (1/(1-p))\frac{n}{\log n}. \] This result improves the estimation of \(\chi (G_ p)\) presented in \textit{D. W. Matula} [ibid. 7, 275-284 (1987; Zbl 0648.05049)] and is best possible. Further, some results concerning independent sets and the chromatic number of graphs \(G_ p\) for varying probabilities are sketched.