Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Dòng không bằng 15 trong các đồ thị hai chiều có 3 cạnh kết nối
Tóm tắt
Bouchet đã suy đoán rằng mọi đồ thị hai chiều nào cho phép một dòng k không bằng không đều sẽ cho phép một dòng 6 không bằng không. Ông đã chứng minh rằng nghi vấn này đúng khi thay thế 6 bằng 216. Zyka đã cải thiện kết quả với việc thay thế 6 bằng 30. Xu và Zhang đã chỉ ra rằng nghi vấn này đúng với các đồ thị có 6 cạnh kết nối. Và với các đồ thị có 4 cạnh kết nối, Raspaud và Zhu đã chứng minh rằng nó đúng với việc thay thế 6 bằng 4. Trong bài báo này, chúng tôi chỉ ra rằng nghi vấn của Bouchet là đúng khi thay thế 6 bằng 15 cho các đồ thị có 3 cạnh kết nối.
Từ khóa
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