Clique coloring of binomial random graphs
Mcdiarmid, Colin ; Mitsche, Dieter ; Prałat, Paweł
HAL, hal-02083918 / Harvested from HAL
Text on HAL
A clique colouring of a graph is a colouring of the vertices so that no maximal clique is monochromatic (ignoring isolated vertices). The smallest number of colours in such a colouring is the clique chromatic number. In this paper, we study the asymptotic behaviour of the clique chromatic number of the random graph G(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.
Publié le : 2019-07-06
Classification:  [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO],  [MATH.MATH-PR]Mathematics [math]/Probability [math.PR] 
@article{hal-02083918,
     author = {Mcdiarmid, Colin and Mitsche, Dieter and Pra\l at, Pawe\l },
     title = {Clique coloring of binomial random graphs},
     journal = {HAL},
     volume = {6},
     number = {0},
     year = {6},
     language = {en},
     url = {http://dml.mathdoc.fr/item/hal-02083918}
}

Mcdiarmid, Colin; Mitsche, Dieter; Prałat, Paweł. Clique coloring of binomial random graphs. HAL, Tome 6 (6) no. 0, . http://gdmltest.u-ga.fr/item/hal-02083918/