Tight constant for clique chromatic G(n,½)
Informal Conjecture on Tight Constant for Clique Chromatic Number · arXiv:1612.06539
Status solved high confidence
Demidovich and Zhukovskii (arXiv 2020, JGT 2023) fully resolve the conjecture, proving that $\chi_c(G(n,1/2)) = (1/2)\log_2 n - \Theta(\ln \ln n)$ whp. This confirms the conjectured leading constant of $1/2$ and in fact establishes a tight concentration result that sharply pins down the second-order term as well.
Cited literature (1)
-
Proves $\chi_c(G(n,1/2)) = (1/2)\log_2 n - \Theta(\ln \ln n)$ whp (arXiv December 2020), confirming the conjectured leading constant 1/2 and obtaining a tight concentration result.
Reviewer notes. The conjecture is fully resolved by Demidovich and Zhukovskii. Their result is strictly sharper than the conjectured (1/2+o(1))log n form, as they pin down the second-order term Theta(ln ln n) as well. The arXiv preprint appeared December 2020; the journal version in JGT appeared 2023.
Context
The paper establishes $\chi_c(G(n,1/2)) = \Theta(\log n)$ whp, with the upper bound $(1/2+o(1))\log_2 n$ coming from McDiarmid–Mitsche–Pratat. The authors note that the constant $\frac{1}{2000}$ in their lower bound can certainly be improved but that the method as presented does not suffice to pin down the tight constant.
Notes. Stated in the concluding remarks without a labelled environment, using the phrase 'It seems plausible that'. All logarithms in the paper are base 2 unless otherwise specified. PDF source.
Source paper
Clique coloring of dense random graphs
Noga Alon, Michael Krivelevich · 2017-11-05
https://arxiv.org/abs/1612.06539
PDF source