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., University of Vermont, Burlington, VT 05401-1455 USA

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

December 2003