EDGE COLORINGS IN BIPARTITE GRAPHES
RAND CORP SANTA MONICA CA
Pagination or Media Count:
The problem studied in this paper is that of determining conditions for color-feasibility of a list P in a bipartite graph G. Necessary and sufficient conditions are obtained in case the n-list P contains at most two distinct positive integers. It is shown that these conditions while necessary in the general case are not sufficient if P contains three or more distinct positive integers. For the case of two distinct integers in P, the method of proof leads to an efficient edge-coloring algorithm. The main results can be interpreted in terms of sum decompositions of 0,1-matrices or in terms of multicommodity flows in certain kinds of directed networks.
- Theoretical Mathematics