Abstract:

A nowhere-zero $k$-flow on a graph $G=(V(G), E(G))$ is a pair $(D, f)$, where $D$ is an orientation on $E(G)$ and $f\colon E(G)\to \{\pm1, \pm2, \cdots, \pm(k-1)\}$ is a function such that the total outflow equals to the total inflow at each vertex. This concept was introduced by Tutte as an extension of face colorings, and Tutte in 1954 conjectured that every bridgeless graph admits a nowhere-zero 5-flow, known as the 5-Flow Conjecture. This conjecture is verified for some graph classes and remains unresolved as of today. In this paper, we show that every bridgeless graph of Euler genus at most 20 admits a nowhere-zero 5-flow, which improves several known results.

Key words: 5-flow conjecture, minimal counterexample, graphs with bounded genus