Abstract: Graph coloring is one of several constraint satisfaction problems that are studied on random structures The problem at the heart of this talk is to identify the chromatic number of a random d-regular graph