chromatic index

The edge chromatic number, sometimes also called the chromatic index, of a graph G is fewest number of colors necessary to color each edge of G such that no two edges incident on the same vertex have the same color. In other words, it is the number of distinct colors in a minimum edge coloring. The edge chromatic number of a graph must be at least Δ, the maximum vertex degree of the graph. However, Vizing and Gupta showed that any graph can be edge-colored with at most Δ + 1 colors. There are therefore precisely two classes of graphs: those with edge chromatic number equal to Δ (class 1 graphs) and those with edge chromatic number equal to Δ + 1 (class 2 graphs).

chromatic number | class 1 graph | class 2 graph | edge coloring | maximum vertex degree | minimum edge coloring | snark | Vizing's theorem