Given a set of connection requests in a WDM optical network and a designated lightpath for each connection request, the wavelength assignment problem is to assign a wavelength to each lightpath in such a way that light-paths sharing common links are assigned different wavelengths and the number of wavelengths used is minimized. The main result of the paper is to show that there exist simple heuristic wavelength assignment algorithms whose average-case performance is very close to the optimum. Our strategy is to convert wavelength assignment on an optical network with randomly generated connection requests into vertex coloring on a random lightpath graph.