**Bouchet's 6-Flow
Conjecture **

A *k-flow* in a graph assigns to each edge a direction and a value *0,1,
... ,k-1* such that at each vertex the sum of the flows directed in equals
the sum of the flows directed out. The flow is *nowhere-zero* if zero is
not assigned to an edge. Seymour has proven that every bridgeless graph has a
nowhere-zero 6-flow.

Bouchet has studied the following generalization. A *bidirected graph*
assigns each end of each edge an arrow either directed into our out of that
vertex. A *k-flow* on a bidirected graph is required to have the flow into
each vertex equal to the flow out of that vertex. If the bidirection on the
edges has one end of each edge with an arrow pointing in and the other end with
an arrow pointing out, then the concept of a *k*-flow on a bidirected
graph reduces to the usual concept of a *k*-flow on the underlying graph.
If both arrows point in at the ends of some edge, or both point out, the two
concepts are different.

**Conjecture:** *Every bidirected graph has a nowhere-zero 6-flow. *

Bouchet arrived at the idea as a dual to local tension on a graph embedded on a non-orientable surface. It is known [D] that every bidirected graph has a nowhere-zero 12-flow, and that every 4-edge-connected bidirected graph with a nowhere-zero integer flow also has a nowhere-zero 4-flow.

**References: **

[B] A. Bouchet, Nowhere-zero integral flows on a bidirected
graph, *J. Combin. Theory Ser. B* **34** (1983) 279-292.

[D] M. DeVos, Flows on bidirected graphs, preprint.

Submitted by: Dan Archdeacon, Dept. of Math. and Stat.,

Send comments to *dan.archdeacon@uvm.edu*
(with thanks to Matt DeVos, see http://www.math.princeton.edu/~matdevos/open/bouchet.html)

December 2003