Clique coloring of dense random graphs

Noga Alon, Michael Krivelevich

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


The clique chromatic number of a graph G=(V.E) is the minimum number of colors in a vertex coloring so that no maximal (with respect to containment) clique is monochromatic. We prove that the clique chromatic number of the binomial random graph G=G(n,1/2) is, with high probability, Ω(log n). This settles a problem of McDiarmid, Mitsche, and Prałat who proved that it is O(log n) with high probability.

Original languageEnglish (US)
Pages (from-to)428-433
Number of pages6
JournalJournal of Graph Theory
Issue number3
StatePublished - Jul 2018
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Geometry and Topology


  • cliques
  • coloring
  • random graphs


Dive into the research topics of 'Clique coloring of dense random graphs'. Together they form a unique fingerprint.

Cite this