EDGE COLORINGS IN BIPARTITE GRAPHES

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1966
Accession Number
AD0637202

Entities

People

  • D. R. Fulkerson
  • Jon Folkman

Organizations

  • RAND Corporation

Tags

DTIC Thesaurus Topics

  • Air Force
  • Continents
  • Decomposition
  • Flow Network
  • Geographic Regions
  • Graphs
  • Inequalities
  • Intervals
  • North America
  • Permutations
  • Sequences
  • United States

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.
  • Operations Research