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.

Finding the minimum edge coloring of a graph is equivalent to finding the minimum
vertex coloring of its line graph (Skiena 1990, p. 216).