The Clique Chromatic Number of Sparse Random Graphs

ABSTRACT 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 for most edge‐probabilities in the range . 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 in some ranges, and discover a surprising new phenomenon that contradicts earlier predictions for edge‐probabilities close to .