An edge coloring of a graph G is a coloring of the edges of G 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 G is equivalent to finding the minimum vertex coloring of its line graph L(G). Computation of a minimum edge coloring of a graph is implemented in the Wolfram Language as FindEdgeColoring[g]. The edge chromatic number gives the minimum number of colors with which a graph can be colored, i.e., the number of colors in a minimum edge coloring.

chromatic number | edge chromatic number | edge coloring | graph coloring | k-coloring | labeled graph | minimum vertex coloring | vertex coloring