Purchase Print Copy

 FormatList Price Price
Add to Cart Paperback33 pages $20.00 $16.00 20% Web Discount

The determination of conditions for color-feasibility of a list of nonnegative integers, P, in a bipartite graph, G. Necesssary 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 also be interpreted in terms of sum decompositions of (0, 1)-matrices or in terms of multicommodity flows in certain kinds of connected networks.

This report is part of the RAND Corporation research memorandum series. The Research Memorandum was a product of the RAND Corporation from 1948 to 1973 that represented working papers meant to report current results of RAND research to appropriate audiences.

The RAND Corporation is a nonprofit institution that helps improve policy and decisionmaking through research and analysis. RAND's publications do not necessarily reflect the opinions of its research clients and sponsors.