Nowhere-zero 15-flow in 3-edge-connected bidirected graphs
Tóm tắt
It was conjectured by Bouchet that every bidirected graph which admits a nowhere-zero k flow will admit a nowhere-zero 6-flow. He proved that the conjecture is true when 6 is replaced by 216. Zyka improved the result with 6 replaced by 30. Xu and Zhang showed that the conjecture is true for 6-edge-connected graphs. And for 4-edge-connected graphs, Raspaud and Zhu proved it is true with 6 replaced by 4. In this paper, we show that Bouchet’s conjecture is true with 6 replaced by 15 for 3-edge-connected graphs.
Tài liệu tham khảo
Bouchet, A.: Nowhere-zero integer flows on bidirected graphs. J. Combin. Theory Ser. B, 34, 279–292 (1983)
Jaeger, F.: Flows and generalized coloring theorems in graphs. J. Combin. Theory Ser. B, 26, 205–216 (1979)
Khelladi, A.: Nowhere-zero integer chains and flows in bidirected graphs. J. Combin. Theory Ser. B, 43, 95–115 (1987)
Korte, B., Vygen, J.: Combinatorial Optimization Theory and Algorithms, Springer, Berlin, 2006
Raspaud, A., Zhu, X.: Circular flow on signed graphs. J. Combin. Theory Ser. B, 101, 464–479 (2011)
Seymour, P. D.: Nowhere-zero 6-flows. J. Combin. Theory Ser. B, 30, 130–135 (1981)
Thomassen, C.: 2-linked graphs. Europ. J. Combinatorics, 1, 371–378 (1980)
Toft, B., Jensen, T. R.: Graph Coloring Problems, Wiley, New York, 1995
Tutte, W. T.: On the imbedding of linear graphs in surfaces. Proc. London Math. Soc., 51, 474–483 (1949)
Wei, E., Tang, W., Wang, X.: Flows in 3-edge-connected bidirected graphs. Front. Math. China, 6, 339–348 (2011)
Xu, R., Zhang, C. Q.: On flows in bidirected graphs. Discrete Math., 299, 335–343 (2005)
Zyka, O.: Nowhere-zero 30-flows on bidirected graphs, Thesis, Charles University, Praha, 1987