论文标题
集团变色的密集渐近渐近图密集的随机图
Tight asymptotics of clique-chromatic numbers of dense random graphs
论文作者
论文摘要
图形的集合色数是将分配给其顶点集所需的最小颜色数，因此不包含最大集合是单色的。 McDiarmid，Mitsche和Prałat证明了二项式随机图的集团$ g \ left（n，\ frac {1} {1} {2} {2} \右）$最多是$ \ left（\ frac {1} {1} {2} {2} {2}+o（offor）。 Alon和Krivelevich表明，它大于$ \ frac {1} {2000} \ log_2n $具有高概率，并建议对数面前的正确常数是$ \ frac {1} {2} {2} {2} {2} {2} $ $，我们证明了他们的猜测，并获得紧密的浓度结果：WHP。 $χ_c\ left（g \ left（n，1/2 \ right）\ right）= \ frac {1} {2} {2} \ log_2 n -θ\ left（\ ln \ ln n n \ right）。$
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 Prałat proved that the clique chromatic number of the binomial random graph $G\left(n,\frac{1}{2}\right) $ is at most $\left(\frac{1}{2}+o(1)\right)\log_2n$ with high probability. Alon and Krivelevich showed that it is greater than $\frac{1}{2000}\log_2n$ with high probability and suggested that the right constant in front of the logarithm is $\frac{1}{2}.$ We prove their conjecture and, beyond that, obtain a tight concentration result: whp $χ_c\left(G\left(n,1/2\right)\right) = \frac{1}{2}\log_2 n - Θ\left(\ln\ln n\right).$
