next up previous contents index CD CD Algorithms
Next: Graph Isomorphism Up: Graph Problems: Hard Problems Previous: Vertex Coloring

Edge Coloring



Input description: A graph G=(V,E).

Problem description: What is the smallest set of colors needed to color the edges of E such that no two same-color edges share a vertex in common?

Discussion: The edge coloring of graphs arises in a variety of scheduling applications, typically associated with minimizing the number of noninterfering rounds needed to complete a given set of tasks.   For example, consider a situation where we need to schedule a given set of two-person interviews, where each interview takes one hour. All meetings could be scheduled to occur at distinct times to avoid conflicts, but it is less wasteful to schedule nonconflicting events simultaneously. We can construct a graph whose vertices are the people and whose edges represent the pairs of people who want to meet. An edge coloring of this graph defines the schedule. The color classes represent the different time periods in the schedule, with all meetings of the same color happening simultaneously.   

The National Football League solves such an edge coloring problem each season to make up its schedule.   Each team's opponents are determined by the records of the previous season.   Assigning the opponents to weeks of the season is the edge-coloring problem, presumably complicated by the constraints of spacing out rematches and making sure that there is a good game every Monday night.

The minimum number of colors needed to edge color a graph is called by some its edge-chromatic number and others its chromatic index.     To gain insight into edge coloring, note that a graph consisting of an even-length cycle can be edge-colored with 2 colors, while odd-length cycles have an edge-chromatic number of 3.

Edge coloring has a better (if less famous) theorem associated with it than does vertex coloring.   Vizing's theorem states that any graph with a maximum vertex degree of tex2html_wrap_inline29592 can be edge colored using at most tex2html_wrap_inline29594 colors. To put this in perspective, note that any edge coloring must have at least tex2html_wrap_inline29596 colors, since each of the edges incident on any vertex must be distinct colors.

Further, the proof of Vizing's theorem is constructive and can be turned into an tex2html_wrap_inline29598 algorithm to find an edge-coloring with tex2html_wrap_inline29600 colors, which gives us an edge coloring using at most one extra color. Since it is NP-complete to decide whether we can save this one color, it hardly seems worth the effort to worry about it. An implementation of Vizing's theorem is described below.

Any edge coloring problem on G can be converted to the problem of finding     a vertex coloring on the line graph L(G), which has a vertex of L(G) for each edge of G and an edge of L(G) if and only if the two edges of G share a common vertex. Line graphs can be constructed in time linear to their size, and any vertex coloring code from Section gif can be employed to color them.

Although any edge coloring problem can be so formulated as a vertex coloring problem, this is usually a bad idea, since the edge coloring problem is easier to solve. Vizing's theorem is our reward for the extra thought needed to see that we have an edge coloring problem.

Implementations: Yan Dong produced an implementation of Vizing's theorem in C++ as a course project for my algorithms course while a student at Stony Brook.     It can be found on the algorithm repository WWW site tex2html_wrap_inline29608 algorith, as can an alternative program by Mark Goldberg and Amir Sehic.

Combinatorica [Ski90] provides Mathematica implementations of edge coloring, via the line graph transformation and vertex coloring routines.     See Section gif for further information on Combinatorica.

Notes: Graph-theoretic results on edge coloring are surveyed in [FW77]. Vizing [Viz64] and Gupta [Gup66] both proved that any graph can be edge colored using at most tex2html_wrap_inline29610 colors. Despite these tight bounds, Holyer [Hol81] proved that computing the edge-chromatic number is NP-complete.

Whitney, in introducing line graphs [Whi32], showed that with the exception of tex2html_wrap_inline29612 and tex2html_wrap_inline29614 , any two connected graphs with isomorphic line graphs are isomorphic. It is an interesting exercise to show that     the line graph of an Eulerian graph is both Eulerian and Hamiltonian, while the line graph of a Hamiltonian graph is always Hamiltonian.

Related Problems: Vertex coloring (see page gif), scheduling (see page gif).    

next up previous contents index CD CD Algorithms
Next: Graph Isomorphism Up: Graph Problems: Hard Problems Previous: Vertex Coloring

Mon Jun 2 23:33:50 EDT 1997