Skip to Main content Skip to Navigation
Journal articles

Clique coloring of binomial random graphs

Abstract : 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.
Complete list of metadata

Cited literature [26 references]  Display  Hide  Download
Contributor : Dieter Mitsche Connect in order to contact the contributor
Submitted on : Friday, March 29, 2019 - 11:52:29 AM
Last modification on : Tuesday, January 4, 2022 - 3:54:25 AM


Files produced by the author(s)




Colin Mcdiarmid, Dieter Mitsche, Paweł Prałat. Clique coloring of binomial random graphs. Random Structures and Algorithms, Wiley, 2018, ⟨10.1002/rsa.20804⟩. ⟨hal-02083918⟩



Les métriques sont temporairement indisponibles