Article ID Journal Published Year Pages File Type
4656694 Journal of Combinatorial Theory, Series B 2016 73 Pages PDF
Abstract

Let G(n,d)G(n,d) be the random d-regular graph on n vertices. For every integer k   exceeding a certain constant k0k0 we identify a number dk-coldk-col such that G(n,d)G(n,d) is k  -colorable w.h.p. if ddk-cold>dk-col.

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Preview
On the chromatic number of random regular graphs
Authors
, , ,