(2 + epsilon)-flows

A flow on a graph assigns
a direction to each edge e
and a value phi(e) to that
directed edge such that at each edge, the sum of the flow into that
vertex equals the flow out of that vertex. Usually the flows are
required to be integered values, but we allow real-valued flows. The
goal is to get a flow where all of the values are as equal as possible.
At first glance this would appear to be impossible: a vertex of odd
degree cannot have the same number of edges giving a flow in than as
edges giving a flow out. However, this can be roughly balanced if the
indegree and the outdegree are both large. In particular, we might be
possible to get the flows between 1 and 1+epsilon provided that the degrees
are sufficiently large. The same type of argument applies over small
edge cuts, so we want large edge connectivity.

The problem is phrased precisely as follows. An x-flow on the graph gives a
direction and a flow to each edge, where the flow is at least 1 and at
most x-1. So a (2+epsilon)-flow has values between
1 and 1+epsilon. The following
is due to Goddyn and Seymour, and is called the (2+epsilon)-flow Conjecture.

Conjecture: For every epsilon > 0, there is a k>0 such that every k-edge-connected graph has a (2+epsilon)-flow.

The conjecture is true for planar graphs [KZ]. I believe it is true in general.References:

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

Submitted by: Dan Archdeacon, Department of Mathematics and
Statistics, University of Vermont, Burlington VT 05405 USA. (with
thanks to Matt DeVos)

Send comments to *dan.archdeacon@uvm.edu*

December 2003.