Bounded-excess flows in cubic graphs

An (r, α)-bounded-excess flow ((r, α)-flow) in an orientation of a graph G = (V, E) is an assignment f : E → [1, r−1], such that for every vertex x ∈ V, $|{\sum }_{e\in E^{+}\left(x\right)}f\left(e\right)-{\sum }_{e\in E^{-}\left(x\right)}f\left(e\right)|\le \alpha$. E⁺(x), respectively E⁻(x), is the set of edges directed from, respectively toward x. Bounded-excess flows suggest a generalization of Circular nowhere-zero flows (cnzf), which can be regarded as (r, 0)-flows. We define (r, α) as Stronger or equivalent to (s, β), if the existence of an (r, α)-flow in a cubic graph always implies the existence of an (s, β)-flow in the same graph. We then study the structure of the bounded-excess flow strength poset. Among other results, we define the Trace of a point in the r − α plane by $tr\left(r,\alpha \right)=\frac{r-2\alpha }{1-\alpha }$ and prove that among points with the same trace the stronger is the one with the smaller α (and larger r). For example, if a cubic graph admits a k-nzf (trace k with α = 0), then it admits an $(r,\frac{k-r}{k-2})$-flow for every r, 2 ≤ r ≤ k. A significant part of the article is devoted to proving the main result: Every cubic graph admits a $(3\frac{1}{2},\frac{1}{2})$-flow, and there exists a graph which does not admit any stronger bounded-excess flow. Notice that $tr(3\frac{1}{2},\frac{1}{2})=5$ so it can be considered a step in the direction of the 5-flow Conjecture. Our result is the best possible for all cubic graphs while the seemingly stronger 5-flow Conjecture relates only to bridgeless graphs. We also show that if the circular-flow number of a cubic graph is strictly less than 5, then it admits a $(3\frac{1}{3},\frac{1}{3})$-flow (trace 4). We conjecture such a flow to exist in every cubic graph with a perfect matching, other than the Petersen graph. This conjecture is a stronger version of the Ban-Linial Conjecture [1]. Our work here strongly relies on the notion of Orientable k-weak bisections, a certain type of k-weak bisections. k-Weak bisections are defined and studied by L. Esperet, G. Mazzuoccolo, and M. Tarsi [4].