The Chromatic Number of Random Regular Graphs
classification
❄️ cond-mat.dis-nn
cond-mat.stat-mechmath.COmath.PR
keywords
chromaticnumberintegerrandomd-regulareithergivengraph
read the original abstract
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) \log k < d < 2k \log k then the chromatic number is either k+1 or k+2.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.