… A lower bound of 3.003 is announced in [5], improving the earlier bound of 2.99 given in [2].
In this paper we obtain a small improvement in the upper bound for the phase transition
threshold in 3colouring n-vertex graphs. An elementary “first-moment” method suffices to
show that if m(G) is the degree sum of an n-vertex graph G, then “almost all” graphs with m(G)/n
> 5.419 are not 3-vertex colourable. We develop the technique discovered by [ 81, in order
to reduce this to 5.2057. … In this paper a new upper bound on the non-3-colourability …