The Chromatic Number of Random Regular Graphs

The Chromatic Number of Random Regular Graphs
复制标题

随机正则图的色数

DOI：
--
复制
发表时间：
2004
期刊：
International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
影响因子：
--
通讯作者：
Cristopher Moore
Cristopher Moore
中科院分区：
--
文献类型：
--
作者：
D. Achlioptas;Cristopher Moore

文献摘要

被引文献

相似文献

给定任意整数d ≥ 3，设k是使得d < 2k log k的最小整数。我们证明了随机d-正则图的色数很可能是k，k+1，或k+2。
Given any integer d ≥ 3, let k be the smallest integer such that d < 2k log k. We prove that with high probability the chromatic number of a random d-regular graph is k, k+1, or k+2.