  The clique chromatic number of a graph is the smallest number of colors in a
vertex coloring so that no maximal clique is monochromatic. In this paper, we
determine the order of magnitude of the clique chromatic number of the random
graph G_{n,p} for most edge-probabilities p in the range n^{-2/5} \ll p \ll 1.
This resolves open problems and questions of Lichev, Mitsche and Warnke as well
as Alon and Krievelevich.
  One major proof difficulty stems from high-degree vertices, which prevent
maximal cliques in their neighborhoods: we deal with these vertices by an
intricate union bound argument, that combines the probabilistic method with new
degree counting arguments in order to enable Janson's inequality. This way we
determine the asymptotics of the clique chromatic number of G_{n,p} in some
ranges, and discover a surprising new phenomenon that contradicts earlier
predictions for edge-probabilities p close to n^{-2/5}.
