Importance: High ✭✭✭
 Author(s): Goddyn, Luis A. Seymour, Paul D.
 Subject: Graph Theory » Coloring » » Nowhere-zero flows
 Keywords: edge-connectivity flow
 Prize: none
 Posted by: mdevos on: March 7th, 2007
Conjecture   For every there exists an integer so that every -edge-connected graph has a -flow.

Definition: If is a directed graph and , a real -flow (sometimes abbreviated -flow) of is a real valued flow with the property that for every . As in the case of nowhere-zero flows, the existence of an -flow in a graph does not depend on the orientation, and we say that an undirected graph has an -flow if some (and thus every) orientation of it admits such a flow. It is a simple exercise to prove that every graph with a real -flow has an (integer) nowhere-zero -flow where . Thus, we may view -flows as a refinement of nowhere-zero -flows.

This conjecture has a strong intuitive appeal. Simply put, the above conjecture asserts that in a graph with high edge-connectivity, it is possible to find a real-valued flow where every edge has about the same flow value. By the above comment relating -flows and nowhere-zero -flows, this conjecture (if true) would imply The weak 3-flow conjecture (See 3-flow conjecture). Zhang [Z] has proved that this result holds when restricted to graphs on a fixed surface, but little else seems to be known.

## Bibliography

[KZ] W. Klostermeyer and C. Q. Zhang, -coloring of planar graphs with large odd-girth. Graph Theory 33 (2000), no. 2, 109--119. MathSciNet

[Z] C. Q. Zhang, Cun Quan, Circular flows of nearly Eulerian graphs and vertex-splitting. J. Graph Theory 40 (2002), no. 3, 147--161. MathSciNet

* indicates original appearance(s) of problem.