TOPICS
Search

Edge Chromatic Number


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 Delta, 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 Delta+1 colors. There are therefore precisely two classes of graphs: those with edge chromatic number equal to Delta (class 1 graphs) and those with edge chromatic number equal to Delta+1 (class 2 graphs).

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

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


See also

Chromatic Number, Class 1 Graph, Class 2 Graph, Edge Coloring, Maximum Vertex Degree, Minimum Edge Coloring, Snark, Vizing's Theorem

Explore with Wolfram|Alpha

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 p-Graph" [Russian]. Diskret. Analiz 3, 23-30, 1964.

Referenced on Wolfram|Alpha

Edge Chromatic Number

Cite this as:

Weisstein, Eric W. "Edge Chromatic Number." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/EdgeChromaticNumber.html

Subject classifications