Open Problem Garden

Definition: A bidirected graph is a graph in which every edge has two arrowheads, one next to each endpoint. If the edge has ends and , then the arrowheads nearest and may point either toward or toward (giving four possibilities in all). If is a bidirected graph, a -flow of G is a map with the property that at every vertex, the sum of on the edges whose ends at are directed into is equal to the sum of on the edges whose ends at are directed out of . We say that is nowhere-zero if for every (see nowhere-zero flows).

Flows on bidirected graphs arise naturally as duals of local-tensions on a non-orientable surface. For more on this relationship, see [B]. Bouchet proved that the above conjecture is true with 6 replaced by 216, and exhibited a bidirected Petersen graph as above which shows that 6 is the best value possible. Zyka [Z] and independently Fouquet improved upon this result proving that the above conjecture is true with 6 replaced by 30. Khelladi [K] proved that for 4-connected graphs, the above conjecture is true with 6 replaced by 18. DeVos [D] proved that the above conjecture holds with 6 replaced by 12, and showed that every 4-edge-connected bidirected graph with a nowhere-zero integer flow also has a nowhere-zero 4-flow.