Tight asymptotics of clique‐chromatic numbers of dense random graphs

DOI10.1002/JGT.22927MaRDI QIDQ6074590zbMATH OpenOpenAlexFDO

Authors Yury A. Demidovich, M. E. Zhukovskii

Publication date 12 October 2023

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

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

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)

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).$

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

Cites work

• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Clique coloring of binomial random graphs
• Clique coloring of dense random graphs
• Clique-transversal sets of line graphs and complements of line graphs
• Coloring the Maximal Cliques of Graphs
• On colouring random graphs
• On the complexity of bicoloring clique hypergraphs of graphs
• Perfect graphs of arbitrarily large clique-chromatic number
• The Grötzsch theorem for the hypergraph of maximal cliques
• The chromatic number of 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)