algorithms for it take exponential time. Many variations of the edge-coloring problem, in which an assignments of colors to edges must satisfy other conditions than non-adjacency, have been studied. Edge colorings have applications in scheduling problems and in frequency assignment for fiber optic networks.

Examples

A cycle graph may have its edges colored with two colors if the length of the cycle is even: simply alternate the two colors around the cycle.

1.Previous
3.Next