Clique coloring of dense random graphs. Issue 3 (28th November 2017)

• Record Type: Journal Article
• Authors: Alon, Noga; Krivelevich, Michael
• Is Part Of: Journal of graph theory. Volume 88:Issue 3(2018)
• Page Start: 428
• Page End: 433
• Publication Date: 2017-11-28
• Subjects: coloring -- cliques -- random graphs; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22222
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: 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.