Clique coloring of dense random graphs

DOI10.1002/JGT.22222MaRDI QIDQ4581274zbMATH OpenOpenAlexFDO

Authors Noga Alon, Michael Krivelevich

Publication date 16 August 2018

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1612.06539

zbMATH Keywords

cliquescoloringrandom graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Density (toughness, etc.) (05C42) Random graphs (graph-theoretic aspects) (05C80)

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, Omega(log n). This settles a problem of McDiarmid, Mitsche and Pralat who proved that it is O(log n) with high probability.

Recommendations

• Tight asymptotics of clique‐chromatic numbers of dense random graphs
• A note on the chromatic number of a dense random graph
• Clique coloring of binomial random graphs
• Tight bounds on the clique chromatic number
• On the Chromatic Number of Random Graphs

Cited in

(10)

• Lower bounds on the clique-chromatic numbers of some distance graphs
• Cliques and chromatic number in multiregime random graphs
• New bounds on clique-chromatic numbers of Johnson graphs
• Clique chromatic numbers of intersection graphs
• Clique coloring of binomial random graphs
• Tight asymptotics of clique‐chromatic numbers of dense random graphs
• The jump of the clique chromatic number of random graphs
• Clique colourings of geometric graphs
• The clique chromatic number of sparse random graphs
• Tight bounds on the clique chromatic number

This page was built for publication: Clique coloring of dense random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4581274)