Frontiers of Mathematics in China >

2011 , Vol. 6 >Issue 2: 339 - 348

DOI: https://doi.org/10.1007/s11464-011-0111-3

RESEARCH ARTICLE

Flows in 3-edge-connected bidirected graphs

  • Erling WEI , 1 ,
  • Wenliang TANG 2 ,
  • Xiaofeng WANG 3
Expand
  • 1. Department of Mathematics, Renmin University of China, Beijing 100872, China
  • 2. Department of Mathematics, West Virginia University, Morgantown, WV 26505, USA
  • 3. Department of Mathematics and Actuarial Sciences, Indiana University Northwest, Gary, IN 46408, USA

Received date: 07 Oct 2010

Accepted date: 12 Jan 2011

Published date: 01 Apr 2011

Copyright

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg
Fold

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.

Key words： Bidirected graph; integer flow; matroid

Cite this article

Erling WEI , Wenliang TANG , Xiaofeng WANG . Flows in 3-edge-connected bidirected graphs[J]. Frontiers of Mathematics in China, 2011 , 6(2) : 339 -348 . DOI: 10.1007/s11464-011-0111-3

References

Publishing order | Descend order by publishing year | Descend order by cited within
1
Bouchet A. Nowhere-zero integer flows on bidirected graphs. J Comb Theory B, 1983, 34: 279-292

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

DOI

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

Options
Outlines

/

〈 〉