Clique coloring of binomial random graphs. Issue 4 (12th November 2018) - McDiarmid, Colin; Mitsche, Dieter; Prałat, Paweł
Abstract : A clique coloring of a graph is a coloring of the vertices so that no maximal clique is monochromatic (ignoring isolated vertices). The smallest number of colors in such a coloring is the clique chromatic number. In this paper, we study the asymptotic behavior of the clique chromatic number of the random graph 𝒢( n, p ) for a wide range of edge‐probabilities p  =  p ( n ). We see that the typical clique chromatic number, as a function of the average degree, forms an intriguing step function.