Clique coloring of binomial random graphs |
| |
Authors: | Colin McDiarmid Dieter Mitsche Pawe Praat |
| |
Institution: | Colin McDiarmid,Dieter Mitsche,Pawe? Pra?at |
| |
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. |
| |
Keywords: | clique chromatic number random graphs |
|
|