On the chromatic number of random regular graphs
On the chromatic number of random regular graphs
复制标题
DOI：
10.1016/j.jctb.2015.09.006
复制
发表时间：
2016-01-01
影响因子：
1.4
通讯作者：
Hetterich, Samuel
中科院分区：
文献类型：
--
作者：
Coja-Oghlan, Amin;Efthymiou, Charilaos;Hetterich, Samuel
设G（n，d）是n阶随机d-正则图。对于每个超过某个常数k（0）的整数k，我们确定一个数4，01，使得G（n，d）如果d < d（k-col）是k-可着色的w. h. p.，如果d> d（k-col）是非k-可着色的w. h. p.。(C)2015 Elsevier Inc. All rights reserved.
Let G(n, d) be the random d-regular graph on n vertices. For every integer k exceeding a certain constant k(0) we identify a number 4,01 such that G(n, d) is k-colorable w.h.p. if d < d(k-col) and non-k-colorable w.h.p. if d> d(k-col). (C) 2015 Elsevier Inc. All rights reserved.