Edge-colouring random graphs (Q1109790)

Let \(G_{n,p}\) be the random graph with vertex set \(V_ n=\{1,2,...,n\}\) in which the \(\binom{n}{2}\) possible edges occur independently with probability p. In this paper it is proved that for any constant p, with \(0<p<1\), \[ P(G_{n,p}\text{ is in class }2)>\exp (- n(\log n+O(\log \log n))). \] If \(p_ n\) denotes the proportion of n- vertex graphs in class 2, that is, such that the chromatic index exceeds the maximum vertex degree, then it is shown that \(n^{- (1/2+\epsilon)n}<p_ n<n^{-(1/8-\epsilon)n}\) for n sufficiently large, which extends a result of \textit{P. Erdős} and \textit{R. J. Wilson} [J. Comb. Theory, Ser. B 23, 255-257 (1977; Zbl 0378.05032)].