Frontiers of Mathematics in China >
Flows in 3-edge-connected bidirected graphs
Received date: 07 Oct 2010
Accepted date: 12 Jan 2011
Published date: 01 Apr 2011
Copyright
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
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
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
|
/
〈 | 〉 |