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).

REFERENCES

Fiorini, S. and Wilson, R. Edge-Colourings of Graphs. Pittman, 1977.

Gupta, R. P. "The Chromatic Index and the Degree of a Graph." Not. Amer. Math. Soc. 13, 719, 1966.

Holyer, I. "The NP-Completeness of Edge Colorings." SIAM J. Comput. 10, 718-720, 1981.

Nemhauser, G. L. and Park, S. "A Polyhedral Approach to Edge Coloring." Operations Res. Lett. 10, 315-322, 1991.

Skiena, S. "Edge Colorings." §5.5.4 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 216, 1990.

Vizing, V. G. "On an Estimate of the Chromatic Class of a -Graph" [Russian]. Diskret. Analiz 3, 23-30, 1964.