An edge-coloring of a Graph is a coloring of the edges of such that adjacent edges (or the edges bounding different regions) receive different colors. Brelaz's Heuristic Algorithm can be used to find a good, but not necessarily minimal, edge-coloring.
See also Brelaz's Heuristic Algorithm, Chromatic Number, k-Coloring
References
Saaty, T. L. and Kainen, P. C. The Four-Color Problem: Assaults and Conquest. New York: Dover, p. 13, 1986.