The Chromatic Number of Random Regular Graphs
Achlioptas, Dimitris · Moore, Cristopher
Original · EN
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, and that if (2k-1) k < d < 2k k then the chromatic number is either k+1 or k+2.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.