Accession Number:

AD0637202

Title:

EDGE COLORINGS IN BIPARTITE GRAPHES

Descriptive Note:

Corporate Author:

RAND CORP SANTA MONICA CA

Personal Author(s):

Report Date:

1966-08-01

Pagination or Media Count:

32.0

Abstract:

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.

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE