  This paper introduces a natural generalization of the classical edge coloring
problem in graphs that provides a useful abstraction for two well-known
problems in multicast switching. We show that the problem is NP-hard and
evaluate the performance of several approximation algorithms, both analytically
and experimentally. We find that for random $\chi$-colorable graphs, the number
of colors used by the best algorithms falls within a small constant factor of
$\chi$, where the constant factor is mainly a function of the ratio of the
number of outputs to inputs. When this ratio is less than 10, the best
algorithms produces solutions that use fewer than $2\chi$ colors. In addition,
one of the algorithms studied finds high quality approximate solutions for any
graph with high probability, where the probability of a low quality solution is
a function only of the random choices made by the algorithm.
