INTEGER FLOWS AND MODULO ORIENTATIONS OF SIGNED GRAPHS.

This paper studies the fundamental relations among integer flows, modulo orientations, integer-valued and real-valued circular flows, and monotonicity of flows in signed graphs. A (signed) graph is modulo-(2p + 1)-orientable if it has an orientation such that the indegree is congruent to the outdegree modulo 2p + 1 at each vertex. An integer-valued 2p+1/p -flow is a flow taking integer values in {±p,± (p+1)} . Extending a fundamental result of Jaeger to signed graphs, we show that a bridgeless signed graph is modulo-(2p+1)-orientable if and only if it admits an integer-valued 2p+1/p-flow. It was conjectured by Raspaud and Zhu that, for any signed graph, the admission of a circular r-flow implies the admission of an integer-valued [r]-flow. Although this conjecture has been disproved in general, it is confirmed in this paper for bridgeless signed graphs if r = 2p+1/p and p ≥ 3. [ABSTRACT FROM AUTHOR]