The acyclic edge chromatic number of A Random d-regular graph Is d+ 1

Jaroslav Nešetřil, Nicholas C. Wormald

Research output: Contribution to journalArticleResearchpeer-review

38 Citations (Scopus)


We prove the theorem from the title: the acyclic edge chromatic number of a random d-regular graph is asymptotically almost surely equal to d + 1. This improves a result of Alon, Sudakov, and Zaks and presents further support for a conjecture that Δ(G) + 2 is the bound for the acyclic edge chromatic number of any graph G. It also represents an analog of a result of Robinson and the second author on edge chromatic number.

Original languageEnglish
Pages (from-to)69-74
Number of pages6
JournalJournal of Graph Theory
Issue number1
Publication statusPublished - May 2005
Externally publishedYes


  • Acyclic coloring
  • Coloring
  • Edge coloring
  • Random graphs
  • Regular graphs

Cite this