Determining the circular flow number of a cubic graph (Q2656904)

Summary: A circular nowhere-zero \(r\)-flow on a bridgeless graph \(G\) is an orientation of the edges and an assignment of real values from \([1, r-1]\) to the edges in such a way that the sum of incoming values equals the sum of outgoing values for every vertex. The circular flow number, \(\phi_c(G)\), of \(G\) is the infimum over all values \(r\) such that \(G\) admits a nowhere-zero \(r\)-flow. A flow has its underlying orientation. If we subtract the number of incoming and the number of outgoing edges for each vertex, we get a mapping \(V(G) \to \mathbb{Z} \), which is its underlying balanced valuation. In this paper we describe efficient and practical polynomial algorithms to turn balanced valuations and orientations into circular nowhere zero \(r\)-flows they underlie with minimal \(r\). Using this algorithm one can determine the circular flow number of a graph by enumerating balanced valuations. For cubic graphs we present an algorithm that determines \(\phi_c(G)\) in case that \(\phi_c(G) \leqslant 5\) in time \(O(2^{0.6\cdot|V(G)|})\). If \(\phi_c(G) > 5\), then the algorithm determines that \(\phi_c(G) > 5\) and thus the graph is a counterexample to Tutte's 5-flow conjecture. The key part is a procedure that generates all (not necessarily proper) 2-vertex-colourings without a monochromatic path on three vertices in \(O(2^{0.6\cdot|V(G)|})\) time. We also prove that there is at most \(2^{0.6\cdot|V(G)|}\) of them.