A new proof of validity of Bouchet's conjecture on Eulerian bidirected graphs

Document Type: Research Paper

Author

University of Tehran

Abstract

Recently, E. M'{a}\v{c}ajov'{a} and M. \v{S}koviera proved that every bidirected Eulerian graph which admits a nowhere zero flow, admits a
nowhere zero $4$-flow. This result shows the validity of Bouchet's nowhere zero conjecture for
Eulerian bidirected graphs. In this paper we prove the same theorem in a different terminology and with a short and simple proof.
More precisely,
we prove that every Eulerian undirected graph which admits a zero-sum flow, admits a zero-sum $4$-flow.
As a conclusion we obtain a shorter proof for the previously mentioned result of M'{a}\v{c}ajov'{a} and \v{S}koviera.

Keywords

Main Subjects


[1] S. Akbari, A. Daemi, O. Hatami, A. Javanmard and A. Mehrabian, Zero-sum ows in regular graphs, Graphs
Combin., 26 (2010) 603-615.

[2] S. Akbari, N. Ghareghani, G. B. Khosrovshahi and A. Mahmo o di, On Zero-Sum 6-ows of Graphs, Linear Algeb. Appl., 430 (2009) 3047-3052.

[3] A. Bouchet, Nowhere-zero integral ows on a bidirected graph, J. Combin. Theory Ser. B., 34 (1983) 279-292.

[4] M. DeVos, Flows in bidirected graphs, arXiv:1310.8406.

[5] P. Hell and X. Zhu, On the Adaptable Chromatic Numb er of Graphs, European J. Combin., 29 (2008) 912-921.

[6] E. Maca jova and M. Skoviera, Nowhere-zero ows on signed Eulerian graphs, arXiv:1408.1703.

[7] D. B. West, Introduction to Graph Theory, Prentice Hall, Inc., Upp er Saddle River, 2001.

[8] O. Zyka, Nowhere-Zero 30 -Flow on Bidirected Graphs, Thesis, Charles University, Praha, 1987.