Clique coloring of dense random graphs. Issue 3 (28th November 2017) - Alon, Noga; Krivelevich, Michael
Abstract: 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, Ω ( log n ) . This settles a problem of McDiarmid, Mitsche, and Prałat who proved that it is O ( log n ) with high probability.