The Chromatic Number of Random Regular Graphs

Simple item page
dc.creatorAchlioptas, Dimitris
dc.creatorMoore, Cristopher
dc.date2004-07-11
dc.date.accessioned2026-07-07T02:59:08Z
dc.date.available2026-07-07T02:59:08Z
dc.descriptionGiven 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.
dc.identifierhttps://arxiv.org/abs/cond-mat/0407278
dc.identifierhttp://arxiv.org/abs/cond-mat/0407278
dc.identifierProc. RANDOM 2004
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/24397
dc.subjectDisordered Systems and Neural Networks
dc.subjectStatistical Mechanics
dc.subjectCombinatorics
dc.subjectProbability
dc.titleThe Chromatic Number of Random Regular Graphs
dc.typetext

Files

Collections

arXiv