Edge Chromatic Number

The edge chromatic number, sometimes also called the chromatic index, of a graph is fewest number of colors necessary to color each edge of 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 (Skiena 1990, p. 216). However, Vizing (1964) and Gupta (1966) showed that any graph can be edge-colored with at most 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 (class 2 graphs).

By definition, the edge chromatic number of a graph equals the (vertex) chromatic number of the line graph .

Computation of the edge chromatic number of a graph is implemented in the Wolfram Language as EdgeChromaticNumber[g]. Precomputed edge chromatic numbers for many named graphs can be obtained using GraphData[graph, "EdgeChromaticNumber"].

The edge chromatic number of a bipartite graph is , so all bipartite graphs are class 1 graphs.

Determining the edge chromatic number of a graph is an NP-complete problem (Holyer 1981; Skiena 1990, p. 216).