research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Article
Entered by:
TitleOn the Chromatic Number of a Random 5-Regular Graph
Bibtex cite IDRACTI-RU1-2009-30
Journal Journal of Graph Theory
Year published 2009
Month April
Keywords random graph,random regular graph,chromatic number
It was only recently shown by Shi and Wormald, using the differential equation method to analyze an appropriate algorithm, that a random 5-regular graph asymptotically almost surely has chromatic number at most 4. Here, we show that the chromatic number of a random 5-regular graph is asymptotically almost surely equal to 3, provided a certain four-variable function has a unique maximum at a given point in a bounded domain. We also describe extensive numerical evidence that strongly suggests that the latter condition holds. The proof applies the small subgraph conditioning method to the number of locally rainbow balanced 3-colorings, where a coloring is balanced if the number of vertices of each color is equal, and locally rainbow if every vertex is adjacent to at least one vertex of each of the other colors.
Diaz, Josep
Kaporis, Alexis
Kemkes, G.D
Kirousis, Lefteris
Perez, X
Wormald, Nick
chromatic.pdf (main file)
Publication ID673