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. In: 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. <DissertationTip/>, Cape Town, 1975

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

[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. New York: Wiley, 1995

[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. New York: Marcel Dekker Inc, 1997

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

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg