2020/08/17 by Vahan Mkrtchyan, Mkrtchyan, Vahan
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2008.07152
openalex publication_date 2020/08/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A function f:N→ N is sublinear, if limx→ +∞(f(x))/(x)=0. If A is an Abelian group, G is a graph and ϕ is an A-flow in G, then let N(ϕ) be the nullity of ϕ, that is, the set of edges e of G with ϕ(e)=0. In this paper we show that (a) Tutte's 5-flow conjecture is equivalent to the statement that there is a sublinear function f, such that all 3-edge-connected cubic graphs admit a ℤ5-flow ϕ (not necessarily no-where zero), such that |N(ϕ)|≤ f(|E(G)|); (b) Tutte's 4-flow conjecture is equivalent to the statement that there is a sublinear function f, such that all bridgeless graphs without a Petersen minor admit a ℤ4-flow ϕ (not necessarily no-where zero), such that |N(ϕ)|≤ f(|E(G)|); (c) Tutte's 3-flow conjecture is equivalent to the statement that there is a sublinear function f, such that all 4-edge-connected graphs admit a ℤ3-flow ϕ (not necessarily no-where zero), such that |N(ϕ)|≤ f(|E(G)|).