Minimum Edge Coloring


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) (Skiena 1990, p. 216).

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.

See also

Chromatic Number, Edge Chromatic Number, Edge Coloring, Graph Coloring, k-Coloring, Labeled Graph, Minimum Vertex Coloring, Vertex Coloring

Explore with Wolfram|Alpha


Fiorini, S. and Wilson, R. Edge-Colourings of Graphs. Pittman, 1977.Nemhauser, G. L. and Park, S. "A Polyhedral Approach to Edge Coloring." Operations Res. Lett. 10, 315-322, 1991.Saaty, T. L. and Kainen, P. C. The Four-Color Problem: Assaults and Conquest. New York: Dover, p. 13, 1986.Skiena, S. "Edge Colorings." §5.5.4 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 216, 1990.

Cite this as:

Weisstein, Eric W. "Minimum Edge Coloring." From MathWorld--A Wolfram Web Resource.

Subject classifications