Nowhere-zero $3$-flow and ${\mathbb{Z}}_3$-connectedness in Graphs with Four Edge-disjoint Spanning Trees

Abstract

Given a zero-sum function $\beta :V(G)\to {\mathbb{Z}}_3$ with ${\sum }_{v\in V(G)}\beta (v)=0$, an orientation $D$ of $G$ with $d_D^{+}(v)-d_D^{-}(v)=\beta (v)$ in ${\mathbb{Z}}_3$ for every vertex $v\in V(G)$ is called a $\beta$-orientation. A graph $G$ is ${\mathbb{Z}}_3$-connected if $G$ admits a $\beta$- orientation for every zero-sum function $\beta$. Jaeger et al. conjectured that every $5$-edge-connected graph is ${\mathbb{Z}}_3$-connected. A graph is $⟨{\mathbb{Z}}_3⟩$-extendable at vertex $v$ if any pre-orientation at $v$ can be extended to a $\beta$-orientation of $G$ for any zero-sum function $\beta$. We observe that if every $5$-edge-connected essentially $6$-edge-connected graph is $⟨{\mathbb{Z}}_3⟩$-extendable at any degree five vertex, then the above mentioned conjecture by Jaeger et al. holds as well. Furthermore, applying the partial flow extension method of Thomassen and of Lovász et al., we prove that every graph with at least 4 edge-disjoint spanning trees is ${\mathbb{Z}}_3$-connected. Consequently, every $5$-edge-connected essentially $23$-edge-connected graph is $⟨{\mathbb{Z}}_3⟩$-extendable at degree five vertex.

14 pages, 3 figures