Premium
Integer flows
Author(s) -
Younger D. H.
Publication year - 1983
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190070307
Subject(s) - mathematics , combinatorics , vertex (graph theory) , planar graph , integer (computer science) , graph , flow (mathematics) , undirected graph , discrete mathematics , geometry , computer science , programming language
A k ‐flow is an assignment of edge directions and integer weights in the range 1, …., k – 1 to the edges of an undirected graph so that ateach vertex the flow in is equal to the flow out. This paper gives a polynomial algorithm for finding a 6‐flow that applies uniformly to each graph. The algorithm specializes to give a 5‐flow for planar graphs.