The structure of hereditary properties and colourings of random graphs (Q5928567)

If \({\mathcal P}\) is a non-trivial hereditary graph property, \(0<p<1\), then the \({\mathcal P}\)-chromatic number of \(G_{n,p}\) is a.s. asymptotically \(c_pn/2\log_2 n\) where \(c_p=c_p({\mathcal P})=\lim_{k} c_{k,p}\) and \(P[G_{k,p}\in {\mathcal P}]= 2^{-c_{k,p}{{k}\choose{2}}}\). For this, it is shown that \(c_p({\mathcal P})\) can be approximated to \(c_p({\mathcal P}')\) where \({\mathcal P}'\subseteq {\mathcal P}\) is a class of very simple graphs.