Rich nowhere-zero flows

Abstract: A graph admits a nowhere-zero $k$-flow if its edges can be oriented and assigned values the set $\{1, 2, ..., k-1\}$ in such a way that, at every vertex, the sum of the incoming values equals the sum of the outgoing values. The concept of a nowhere-zero flow is one of the most important concepts in graph theory and has been studied for more than half a century.

In this talk, we introduce -- for cubic graphs -- the notion of a \emph{rich} nowhere-zero $k$-flow: one where the three values at every vertex are pairwise distinct. We conjecture that a cubic graph admits a nowhere-zero $k$-flow if and only if it admits a rich nowhere-zero $(k+1)$-flow. We prove this conjecture for $k=3$ and $k=4$, that is, for bipartite and 3-edge-colourable cubic graphs, respectively. Furthermore, we show that every bridgeless cubic graph admits a rich nowhere-zero 11-flow and conjecture 6 in place of 11 will do.