Bounded‐excess flows in cubic graphs
Michael Tarsi · Journal of Graph Theory · 2020
Abstract 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, . 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 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 ‐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 ‐flow, and there exists a graph which does not admit any stronger bounded‐excess flow. Notice that 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 ‐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].