Tight asymptotics of clique‐chromatic numbers of dense random graphs

DOI10.1002/JGT.22927zbMATH Open1522.05109arXiv2012.03210OpenAlexW3178441973MaRDI QIDQ6074590FDOQ6074590

Authors: Yury A. Demidovich, M. E. Zhukovskii 

Publication date: 12 October 2023

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

Abstract: The clique chromatic number of a graph is the minimum number of colors required to assign to its vertex set so that no inclusion maximal clique is monochromatic. McDiarmid, Mitsche and Pral at proved that the clique chromatic number of the binomial random graph $Gleft(n,frac12ight)$ is at most $left(frac12+o(1)ight)lo{g}_{2}n$ with high probability. Alon and Krivelevich showed that it is greater than $frac12000lo{g}_{2}n$ with high probability and suggested that the right constant in front of the logarithm is $frac12.$ We prove their conjecture and, beyond that, obtain a tight concentration result: whp $ch{i}_{c}left(Gleft(n,1/2ight)ight)=frac12lo{g}_{2}n-Thetaleft(lnlnnight).$

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

Recommendations

• Clique coloring of dense random graphs
• Clique coloring of binomial random graphs
• Tight bounds on the clique chromatic number
• The chromatic number of dense random graphs
• A note on the chromatic number of a dense random graph

zbMATH Keywords

binomial random graphsinclusion maximal clique

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Perfect graphs of arbitrarily large clique-chromatic number
• On colouring random graphs
• The chromatic number of random graphs
• Clique-transversal sets of line graphs and complements of line graphs
• The Grötzsch theorem for the hypergraph of maximal cliques
• Coloring the Maximal Cliques of Graphs
• On the complexity of bicoloring clique hypergraphs of graphs
• Clique coloring of dense random graphs
• Clique coloring of binomial random graphs

Cited In (6)

• Tight bounds on the clique chromatic number
• Asymptotic Structure for the Clique Density Theorem
• The Choice Number of Dense Random Graphs
• Clique coloring of dense random graphs
• The jump of the clique chromatic number of random graphs
• Clique coloring of binomial random graphs

This page was built for publication: Tight asymptotics of clique‐chromatic numbers of dense random graphs

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