On the chromatic number of a random 5-regular graph

J. Díaz, A. C. Kaporis, G. D. Kemkes, L. M. Kirousis, X. Pérez, N. Wormald

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)157-191
Number of pages35
JournalJournal of Graph Theory
Issue number3
StatePublished - Jul 2009


  • Chromatic number
  • Random graph
  • Random regular graph

ASJC Scopus subject areas

  • Geometry and Topology
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'On the chromatic number of a random 5-regular graph'. Together they form a unique fingerprint.

Cite this