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áčajová and M. Š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áčajová and M. Škoviera.

Keywords

Main Subjects

References

[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.

Files

History

  • Receive Date: 07 December 2016
  • Revise Date: 14 March 2017
  • Accept Date: 23 April 2017
  • Published Online: 01 June 2017

Share

How to cite

Statistics