The Chromatic Number of Random Graphs: For Fixed 0 < p < 1, Almost Every G(n,p) Has n/s₀ ≤ χ(G) ≤ (n/s₀)(1 + 3 log log n / log n), where s₀ ≈ 2 log_d n and d = 1/(1−p)Research Paper
The chromatic number of a graph is the least number of colours in a proper vertex colouring. Determining it for a typical graph was, in the words of the paper, "one of the best known and most studied unsolved problems in the theory of random graphs". For the dense random graph with fixed edge probability , the clique number had been known…