×

A new proof of validity of Bouchet’s conjecture on Eulerian bidirected graphs. (English) Zbl 1463.05232

Summary: E. Máčajová and M. Škoviera [SIAM J. Discrete Math. 31, No. 3, 1937–1952 (2017; Zbl 1370.05085)] 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 Škoviera.

MSC:

05C21 Flows in graphs
05C20 Directed graphs (digraphs), tournaments
05C22 Signed and weighted graphs
05C45 Eulerian and Hamiltonian graphs

Citations:

Zbl 1370.05085
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] S. Akbari, A. Daemi, O. Hatami, A. Javanmard and A. Mehrabian, Zero-sum flows in regular graphs,Graphs Combin.,26(2010) 603-615. · Zbl 1231.05117
[2] S. Akbari, N. Ghareghani, G. B. Khosrovshahi and A. Mahmoodi, On Zero-Sum 6-flows of Graphs,Linear Algeb. Appl.,430(2009) 3047-3052. · Zbl 1169.05326
[3] A. Bouchet, Nowhere-zero integral flows on a bidirected graph,J. Combin. Theory Ser. B,34(1983) 279-292. · Zbl 0518.05058
[4] M. DeVos, Flows in bidirected graphs, arXiv:1310.8406.
[5] P. Hell and X. Zhu, On the Adaptable Chromatic Number of Graphs,European J. Combin.,29(2008) 912-921. · Zbl 1147.05031
[6] E. M´aˇcajov´a and M. ˇSkoviera, Nowhere-zero flows on signed Eulerian graphs, arXiv:1408.1703.
[7] D. B. West,Introduction to Graph Theory, Prentice Hall, Inc., Upper Saddle River, 2001.
[8] O. Zyka,Nowhere-Zero30-Flow on Bidirected Graphs, Thesis, Charles University, Praha, 1987.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.