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. An edge coloring containing the smallest possible
number of colors for a given graph is known as a minimum
edge coloring.
A (not necessarily minimum) edge coloring of a graph can be computed using EdgeColoring[g]
in the Wolfram Language package Combinatorica`
.
The edge chromatic number gives the minimum
number of colors with which graph's edges can be colored.