2016/12/20 by Alon, Noga, Krivelevich, Michael
#05C15 #05C80 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1612.06539
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 Pralat who proved that it is O(log n) with high probability.