Flows in 3-edge-connected bidirected graphs

Abstract

It was conjectured by A. Bouchet that every bidirected graph which admits a nowhere-zero k-flow admits a nowhere-zero 6-flow. He proved that the conjecture is true when 6 is replaced by 216. O. Zyka improved the result with 6 replaced by 30. R. Xu and C. Q. Zhang showed that the conjecture is true for 6-edge-connected graph, which is further improved by A. Raspaud and X. Zhu for 4-edge-connected graphs. The main result of this paper improves Zyka’s theorem by showing the existence of a nowhere-zero 25-flow for all 3-edge-connected graphs.

Keywords

Bidirected graph / integer flow / matroid

References

[1] Bouchet A. Nowhere-zero integer flows on bidirected graphs. J Comb Theory B, 1983, 34, 279-292

[2] Jaeger F. On nowhere-zero flows in multigraphs. Proceedings of the Fifth British Combinatorial Conference, Aberdeen, 1975. Congressus Numerantium, 1975, XV, 373-378

[3] Jaeger F. Flows and generalized cloring theorems in graphs. J Comb Theory B, 1979, 26, 205-216

[4] Khelladi A. Nowhere-zero integer chains and flows in bidirected graphs. J Comb Theory B, 1987, 43, 95-115

[5] Kilpatrick P A. Tutte’s first colour-cycle conjecture. Ph D Thesis, Cape Town, 1975

[6] Korte B., Vygen J. Combinatorial Optimization Theory and Algorithms, 2006, Berlin: Springer.

[7] Raspaud A, Zhu X. Circular flow on signed graphs. J Comb Theory B (to appear)

[8] Seymour P. D. Nowhere-zero 6-flows. J Comb Theory B, 1981, 30, 130-135

[9] Toft B., Jensen T. R. Graph Coloring Problems, 1995, New York: Wiley.

[10] Xu R., Zhang C. Q. On flows in bidirected graphs. Discrete Math, 2005, 299, 335-343

[11] Zaslavsky T. Signed graphs. Discrete Applied Math, 1982, 4, 47-74

[12] Zaslavsky T. Orientation of signed graphs. European Journal of Combinatorics, 1991, 12, 361-375

[13] Zhang C. Q. Integer Flows and Cycle Covers of Graphs, 1997, New York: Marcel Dekker Inc.

[14] Zyka O. Nowhere-zero 30-flows on bidirected graphs, 1987, Praha: Charles University.