  The clique chromatic number of a graph G=(V,E) is the minimum number of
colors in a vertex coloring so that no maximal (with respect to containment)
clique is monochromatic. We prove that the clique chromatic number of the
binomial random graph G=G(n,1/2) is, with high probability, \Omega(log n). This
settles a problem of McDiarmid, Mitsche and Pralat who proved that it is O(log
n) with high probability.
