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

https://hal.archives-ouvertes.fr/hal-02083918
Contributor : Dieter Mitsche Connect in order to contact the contributor
Submitted on : Friday, March 29, 2019 - 11:52:29 AM
Last modification on : Thursday, November 25, 2021 - 11:12:10 AM

File

cliquecolouring.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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

Share

Metrics

Record views

66

Files downloads

243