Nowhere‐zero flows in low genus graphs
Martina Möller, Hans Georg Carstens, Gunnar Brinkmann · Journal of Graph Theory · 1988
Abstract A nowhere‐zero k‐flow is an assignment of edge directions and integer weights in the range 1,…, k − 1 to the edges of an undirected graph such that at every vertex the flow in is equal to the flow out. Tutte has conjectured that every bridgeless graph has a nowhere‐zero 5‐flow. We show that a counterexample to this conjecture, minimal in the class of graphs embedded in a surface of fixed genus, has no face‐boundary of length <7. Moreover, in order to prove or disprove Tutte's conjecture for graphs of fixed genus γ, one has to check graphs of order at most 28(γ − 1) in the orientable case and 14(γ − 2) in the nonorientable case. So, in particular, it follows immediately that every bridgeless graph of orientable genus ⩽1 or nonorientable genus ⩽2 has a nowhere‐zero 5‐flow. Using a computer, we checked that all graphs of orientable genus ⩽2 or nonorientable genus ⩽4 have a nowhere‐zero 5‐flow.