ars mathematica contemporanea
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 10 (2016) 91-98
A note on nowhere-zero 3-flow and Z3-connectivity
Fuyuan Chen
Center for Discrete Mathematics, Fuzhou University, Fuzhou, P. R. China, Institute of Statistics and Applied Mathematics, Anhui University of Finance and Economics, Bengbu, 233030, P. R. China
Bo Ning
Department ofApplied Mathematics, School ofScience, Northwestern Polytechnical University, Xi'an, P. R. China,
Center for Applied Mathematics, Tianjin University, 300072, P. R. China Received 22 May 2014, accepted 14 July 2014, published online 8 July 2015
There are many major open problems in integer flow theory, such as Tutte's 3-flow conjecture that every 4-edge-connected graph admits a nowhere-zero 3-flow, Jaeger et al.'s conjecture that every 5-edge-connected graph is Z3-connected and Kochol's conjecture that every bridgeless graph with at most three 3-edge-cuts admits a nowhere-zero 3-flow (an equivalent version of 3-flow conjecture). Thomassen proved that every 8-edge-connected graph is Z3-connected and therefore admits a nowhere-zero 3-flow. Furthermore, Lovdsz, Thomassen, Wu and Zhang improved Thomassen's result to 6-edge-connected graphs. In this paper, we prove that: (1) Every 4-edge-connected graph with at most seven 5-edge-cuts admits a nowhere-zero 3-flow. (2) Every bridgeless graph containing no 5-edge-cuts but at most three 3-edge-cuts admits a nowhere-zero 3-flow. (3) Every 5-edge-connected graph with at most five 5-edge-cuts is Z3-connected. Our main theorems are partial results to Tutte's 3-flow conjecture, Kochol's conjecture and Jaeger et al.'s conjecture, respectively.
Keywords: Integer flow, nowhere-zero 3-flow, Z3-connected, modulo 3-orientation, edge-cuts. Math. Subj. Class.: 05C21, 05C40
E-mail addresses: chenfuyuan19871010@163.com (Fuyuan Chen), ningbo-math84@mail.nwpu.edu.cn (Bo Ning)
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
Abstract
92
Ars Math. Contemp. 10 (2016) 99-112
1 Introduction
All graphs considered in this paper are loopless, but allowed to have multiple edges. A graph G is called k-edge-connected, if G - S is connected for each edge set S with |S| < k. Let X, Y be two disjoint subsets of V(G). Let dG(X, Y) be the set of edges of G with one end in X and the other in Y. In particular, if Y = X, we simply write dG(X) for dG(X, Y), which is the edge-cut of G associated with X. The edge set C = dG(X) is called a k-edge-cut if |dG(X)| = k. If X is nontrivial, we use G/X to denote the graph obtained from G by replacing X by a single vertex x that is incident with all the edges in dG(X).
Let D be an orientation of E(G). The out-cut of D associated with X, denoted by d+ (X), is the set of arcs of D whose tails lie in X. Analogously, the in-cut of D associated with X, denoted by d-(X), is the set of arcs of D whose heads lie in X. We refer to |d+ (X)| and |d-(X)| as the out-degree andin-degree of X, and denote these quantities by
¿¿(X) and ¿¿(X), respectively.
Definition 1.1. (1) An orientation D of E(G) is called a modulo 3-orientation if
¿¿(v) — ¿¿(v) = 0 (mod 3)
for every vertex v G V(G).
(2) A pair (D, f) is called a nowhere-zero 3-flow of G if D is an orientation of E(G) and f is a function from E(G) to {±1, ±2}, such that
E f (e)= E f (e)
e£d+ (v)	e£dD(v)
for every vertex v G V(G).
The 3-flow conjecture, proposed by Tutte as a dual version of Grotzsch's 3-color theorem for planar graphs, may be one of the most major open problems in integer flow theory.
Conjecture 1.2 (3-Flow conjecture, Tutte [9]). Every 4-edge-connected graph admits a nowhere-zero 3-flow.
Kochol proved that Tutte's 3-flow conjecture is equivalent to the following two conjectures.
Conjecture 1.3 (Kochol [4]). Every 5-edge-connected graph admits a nowhere-zero 3-flow.
Conjecture 1.4 (Kochol [5]). Every bridgeless graph with at most three 3-edge-cuts admits a nowhere-zero 3-flow.
A weakened version of Conjecture 1.2, the so-called weak 3-flow conjecture, was proposed by Jaeger.
Conjecture 1.5 (Weak 3-flow conjecture, Jaeger [2]). There is a natural number h such that every h-edge-connected graph admits a nowhere-zero 3-flow.
Lai and Zhang [6] and Alon et al. [1] gave partial results on Conjectures 1.2 and 1.5.
F Chen andB. Ning: A note on nowhere-zero 3-flow and Z3-connectivity
93
Theorem 1.6 (Lai and Zhang [6]). Every 4|"log2 no] -edge-connected graph with at most n0 odd-degree vertices admits a nowhere-zero 3-flow.
Theorem 1.7 (Alon, Linial and Meshulam [1]). Every 2|"log2 n] -edge-connected graph with n vertices admits a nowhere-zero 3-flow.
Recently, Thomassen [8] confirmed weak 3-flow conjecture. He proved
Theorem 1.8 (Thomassen [8]). Every 8-edge-connected graph is Z3-connected and therefore admits a nowhere-zero 3-flow.
Thomassen's method was further refined by Lovâsz, Thomassen, Wu and Zhang [7] to obtain the following theorem.
Theorem 1.9 (Lovâsz, Thomassen, Wu and Zhang [7]). Every 6-edge-connected graph is Z3-connected and therefore admits a nowhere-zero 3-flow.
For more results on Tutte's 3-flow conjecture, we refer the reader to the introduction part of [7] and the book written by Zhang [11].
In this paper, we will give the following conjecture which is equivalent to Tutte's 3-flow conjecture.
Conjecture 1.10. Every 5-edge-connected graph with minimum degree at least 6 has a nowhere-zero 3-flow.
To prove the equivalence of Conjectures 1.2 and 1.10, the following lemma is needed.
Lemma 1.11 (Tutte [10]). Let F (G, k) be the number of nowhere-zero k-flows of G. Then
F (G, k) = F (G/e, k) - F (G \ e, k) if e is not a loop of G.
Proposition 1.12. Conjectures 1.2 and 1.10 are equivalent.
Proof. It is obvious that Conjecture 1.2 implies Conjecture 1.3, and Conjecture 1.3 implies Conjecture 1.10. Now we prove that Conjecture 1.10 can imply Conjecture 1.3. Let G be a 5-edge-connected graph. Let G' be the graph obtained from G by gluing | V(G) | disjoint copies of K7, such that for each such copy Hi, |V (Hi)nV (G)| = 1 (i = 1,2, ••• , |V (G)|). Then G' is 5-edge-connected and its minimum degree is at least 6, and thus has a nowhere-zero 3-flow. By Lemma 1.11, G has a nowhere-zero 3-flow. Therefore Conjecture 1.10 implies Conjecture 1.3. Note that Conjecture 1.2 is equivalent to Conjecture 1.3. This completes the proof.	□
Our first main result is the following theorem.
Theorem 1.13. Let G be a bridgeless graph and let P = {C = dG(X) : |C| = 3, X c V(G)} and Q = {C = dG(X) : |C| = 5, X c V(G)}. If 2|P| + |Q| < 7, then G has a modulo 3-orientation (and therefore has a nowhere-zero 3-flow).
As corollaries of Theorem 1.13, we obtain Theorems 1.14 and 1.15.
Theorem 1.14. Every 4-edge-connected graph with at most seven 5-edge-cuts admits a nowhere-zero 3-flow.
Theorem 1.15. Every bridgeless graph containing no 5-edge-cuts but at most three 3-edge-cuts admits a nowhere-zero 3-flow.
94
Ars Math. Contemp. 10 (2016) 99-112
Remark. The number of 3-edge-cuts in Theorem 1.15 can not be improved from three to four, since K4 or any graph contractable to K4 has no nowhere-zero 3-flow.
Theorems 1.14 and 1.15 partially confirm Conjectures 1.2 and 1.4, respectively. Definition 1.16. (1) A mapping pG : V(G) ^ Zk is called a Zk-boundary of G if
^ ¡3G(v) - 0 (mod k)
vev (G)
(2) A graph G is called Zk-connected, if for every Zk -boundary pG, there is an orientation and a function fpa: E(G) ^ Zk — {0}, such that
f@a (e) —	f@a (e) - (v) (mod k)
e€d~+ (v)	eed-/3a (v)
for every vertex v G V(G).
Jaeger, Linial, Payan and Tarsi [3] conjectured that
Conjecture 1.17 (Jaeger, Linial, Payan and Tarsi [3]). Every 5-edge-connected graph is Z3-connected.
By applying a similar argument as in the proof of Theorem 1.13, we could obtain the second main result, which is a partial result to Conjecture 1.17.
Theorem 1.18. Every 5-edge-connected graph with at most five 5-edge-cuts is Z3-conn-ected.
In the next section, some necessary preliminaries will be given. In Sections 3 and 4, proofs of Theorems 1.13 and 1.18 will be given, respectively.
2 Preliminaries
In this section, we will give additional but necessary notations and definitions, and then give some useful lemmas.
Definition 2.1. Let pG be a Z3-boundary of G. An orientation D of G is called a pG-
orientation if
d+D(v) — dD(v) - Pg(v) (mod 3) for every vertex v G V(G).
Let G be a graph and A be a vertex subset of G. The degree of A, denoted by dG (A), is the number of edges with precisely one end in A. Moreover if A = {x}, we simply write
dG (x).
Let G be a graph and pG be a Z3-boundary of G. Define a mapping tg : V(G) ^
{0, ±1, ±2, ±3} such that, for each vertex x G V(G),
^ (x) = f ^G(x) (mod 3)
TG(X) - \ dG(x) (mod 2).
F Chen andB. Ning: A note on nowhere-zero 3-flow and Z3-connectivity
95
Now, the mapping tg can be further extended to any nonempty vertex subset A as follows:
_ (A) = f MA) (mod 3) tg(a) — \ dG(A) (mod 2).
where £G(A) - £xeA £g(x) e {0,1,2} (mod 3).
Proposition 2.2. Let G be a graph and A be a vertex subset of G.
(1)If	dG(A) < 5, then dG(A) < 4+ |tg(A)|.
(2)	If ¿g(A) > 6, then ¿g(A) > 4+ |tg(A)|.
Proposition 2.2 follows from the fact that |tg(A)| < 3 and dG(A) - |tg(A)| is even.
Lemma 2.3 (Tutte [9]). Let G be a graph.
(1)	G has a nowhere-zero 3-flow if and only if G has a modulo 3-orientation.
(2)	G has a nowhere-zero 3-flow if and only if G has a ¡3 G-orientation with = 0.
The following lemma is Theorem 3.1 in [7] by Lovasz et al. This lemma will play the main role in our proofs.
Lemma 2.4 (Lovasz, Thomassen, Wu and Zhang [7]). Let G be a graph, fiG be a Z3-boundary of G, and let z0 e V(G) and Dz0 be a pre-orientation of E(z0) of all edges incident with z0. Assume that
(i)	|V(G)| > 3.
(ii)	¿g(zo) < 4+ |tg(zo)| and ¿D (zo) - dD (zo) — ^g(zo) (mod 3), and
(iii)	dG(A) > 4 + |tg(A)| for each nonempty vertex subset A not containing z0 with |V(G) \ A| > 1.
Then the pre-orientation Dz0 of E(z0) can be extended to an orientation D of the entire graph G, that is, for every vertex x of G,
¿D (x) — ¿D (x) — pG (x) (mod 3).
3 Proof of Theorem 1.13
If not, suppose that G is a counterexample, such that |V(G)| + |E(G)| is as small as possible. Let P' = {x g V(G) : dG(x) = 3} and Q' = {x G V(G) : dG(x) = 5}.
Claim 3.1. |V(G)| > 3.
Proof. If | V(G) | = 1, then G has a nowhere-zero 3-flow, a contradiction. If | V(G) | = 2, let V(G) = {x, y}, then all the edges of G are all between x and y. Since G is bridgeless, |E(G)| > 2. Let a be the integer in {0,1,2} such that a = |E(G)| - a (mod 3). Orient a edges from x to y and the remaining |E(G)| - a edges from y to x. Clearly, the resulting orientation is a modulo 3-orientation of G, a contradiction. Therefore | V(G) | > 3. □
Claim 3.2. G is 3-edge-connected, and G has no nontrivial 3-edge-cuts.
Proof. If G has a vertex x of degree 2, then suppose that xxi,xx2 G E(G). By the minimality of G, (G — {xx1, xx2}) U {x1x2} has a nowhere-zero 3-flow f '. However, f ' can be extended to a nowhere-zero 3-flow f of G, a contradiction. If G has a nontrivial k-edge-cut (k = 2, 3), then contract one side and find a mod 3-orientation by the minimality of G. Merge such two mod 3-orientations and we will get one for G, a contradiction. □
96
ArsMath. Contemp. 10(2016)91-98
Claim 3.3. For any U c V(G), if dG(U) < 5 and |U| > 2, then U n (P' U Q') = 0.
Proof. If not, choose U to be a minimal one such that: for any A c U with 2 < | A| < |U |, we have dG (A) > 6.
By the minimality of G, G/U has a modulo 3-orientation D' which is a partial modulo 3-orientation of G, such that (x) = dD (x) (mod 3) for each x G V(G) \ U.
Let G' be a graph obtained from G by contracting V(G) \ U as zo and let = 0.
(i)	Since V(G') = U + zo, |V(G')| = |U| + 1 > 3.
(ii)	Since dG'(zo) = dG(U) < 5, by Proposition 2.2 (1), dG'(zo) < 4 + |tG'(zo)|.
(iii)	By the assumption and minimality of U, we have that for any A c U, dG (A) = 5 and dG(A) = 3. If ¿G(a) = 4, then dG' (A) = ¿G(a) = 4 and tG' (A) = fc (a) = £G (A) = 0. Thus dG' (A) = 4 = 4 + |tG' (A) |. If dG (A) > 6, then by Proposition 2.2 (2), dG'(A) = dG(A) > 4+ |tG'(A)|.
By Lemma 2.4, we could see that the pre-orientation of E'(zo) of all edges incident with z0 can be extended to a ,0G'-orientation of G'. Then G has a modulo 3-orientation, which is a contradiction.	□
Let Gi be a graph obtained from G by adding a new vertex z0 and 2|P'| + |Q'| edges between z0 and P' U Q', such that:
(i)	For each vertex v g P', we add two arcs with the same direction between it and z0;
and
(ii)	For each vertex v g Q', we add one arc between it and z0.
If 2|P'| + |Q'| < 5, then all added arcs could be from z0 to P' U Q'. Define £G/ as follows:
(1)	^ (x) = 0 if x G (P' u Q') + zo;
(2)	^ (x) = 1 if x g P';
(3)	^ (x) = 2 if x g Q';
(4)	^ (zo) = 2|P'| + |Q'| (mod 3) and ^ (zo) G {0,1, 2}.
If 2|P'| + |Q'| = 6 or 7, in this case, if |P'| = 0, choose one vertex v G P', such that the two arcs with ends z0 and v are from v to z0, the other arcs incident with z0 are all directed from z0. If |P'| = 0, then two arcs are from Q' to z0, the others verse. Define as follows:
(1)	^ (x) = 0 if x G (P' u Q') + zo;
(2)	(x) = 2 if x G Q' and the arc (zo, x) exists or x G P' and the two arcs with ends zo and x are from x to zo;
(3)	(x) = 1 if x G Q' and the arc (x, zo) exists or x G P' and the two arcs with ends zo and x are from zo to x;
(4)	^g; (zo) = (2|P'| + |Q'| - 2) - 2 (mod 3).
Now dGj(zo) < 4 + |tGi(zo)| and |V(Gi)| = |V(G)| + 1 > 4. We claim that: dG' (A) > 4 + |tG' (A)|, for each nonempty vertex subset A not containing zo with
|V(Gi) \ A| > 1. 1
If A n (P' U Q') = 0, then by Claim 3.3, dG(A) =4 or dG(A) > 6. In each case we could get that dGj (A) = dG(A) > 4 + |tg/ (A)|.
If A n (P ' U Q ') = 0, then by Claim 3.2, dGj (A) > 5. If dGj (A) = 5, then dG(A) = 3 or 4 and |A n (P' U Q')| = 1, and it follows that (A) = 1 or 2, and |tGj (A)| = 1. Thus dG' (A) > 4 + |tG' (A)|. If dG' (A) > 6, by1 Proposition 2.2 (2), we have that dG( (A) > 4+ |tG( (A)|. 1	1
F Chen andB. Ning: A note on nowhere-zero 3-flow and Z3-connectivity
97
Now G[ satisfies all the conditions of Lemma 2.4. By Lemma 2.4, G[ has a ßGt -orientation extended from the pre-orientation of E[ (z0) of all edges incident with z0, which implies that G has a ßG-orientation with ßG = 0. By Lemma 2.3, G has a nowhere-zero 3-flow, which is a contradiction.	□
4 Proof of Theorem 1.18
Assume not. Suppose that G is a counterexample, such that |V(G)| + |E(G)| is as small as possible. Let S' = {x g V(G) : dG(x) = 5} and S = {C = dG(X) : |C| = 5, X c V(G)}. Let be a Z3-boundary, such that G has no -orientation.
Claim 4.1. |V(G)| > 3 and |S'| < |S| < 5.
Proof. Since G is 5-edge-connected, |V(G)| > 2. If |V(G)| = 2, let V(G) = {x, y}, then all the edges of G are between x and y, and |E(G) | > 5. Let Dx be an orientation of x, such thatdD (x)-d^(x) = ftG(x) (mod 3). SinceisaZ3-boundary, d^ (y)-dD (y) = ftG(y) (mod 3). Therefore G has a -orientation, a contradiction. Hence |V(G)| > 3 and |S'| < |S| < 5.	□
Claim 4.2. Let U c V(G) with |U| > 2. If dG(U) = 5, then U n S' = 0.
Proof. If not, choose U to be a minimal one such that: for any A c U with 2 < | A| < |U |, we have dG(A) = 5.
By the minimality of G, G/U has a ftG-orientation D' which is a partial -orientation of G, such that d^, (x) — d^, (x) = ftG(x) (mod 3) for each x g V(G) \ U.
Let G' be a graph obtained from G by contracting V(G) \ U as zo, and let = ftG.
(i)	Since V(G') = U + zo, |V(G')| = |U| + 1 > 3.
(ii)	Since dG,(zo) = dG(U) = 5, by Proposition 2.2 (1), we have that dG,(zo) < 4+ |tg, (zo)|.
(iii)	By the assumption and minimality of U, we have that for any A c U, dG (A) = 5. Therefore dG(A) > 6. By Proposition 2.2 (2), dG' (A) = dG (A) > 4 + |tg' (A)|.
By Lemma 2.4, the pre-orientation of E'(zo) of all edges incident with z0 can be extended to a -orientation of G'. Therefore, G has a -orientation, which is a contradiction.	□
Let Gi be a graph obtained from G by adding a new vertex z0 and |S'| arcs from z0 to S', such that each vertex in S' has degree 6 in Gi.
Define as follows:
(1)	ftGi (x) = ftG(x) if x g s' + zo;
(2)	ftG( (x) = ftG(x) — 1 (mod 3) if x G S';
(3)	ftG1 (zo) = |S'| (mod 3) and ^ (zo) G {0,1, 2}.
Now dG/ (zo) < 4+|tG' (zo)| and |V(Gi)| = |V (G)|+1 > 4. We claim that dGj (A) > 4 + |tg, (A)|, for each nonempty vertex subset A not containing zo with |V(Gi) \ A| > 1.
If A n S' = 0, then by Claim 4.2, dG, (A) = dG(A) = 5. Thus dG, (A) > 6. By Proposition 2.2 (2), dG, (A) > 4 + |tg, (A)(.	1
If A n S' = 0, to dG, (A) > dG(A) + 1 > 6. By Proposition 2.2 (2), we have that dG( (A) > 4+ |tG( (A)|. 1
Now Gi satisfies all the conditions of Lemma 2.4. By Lemma 2.4, Gi has a -orientation extended from the pre-orientation of E' (zo) of all edges incident with zo, which
98
Ars Math. Contemp. 10 (2016) 99-112
implies that G has a pa-orientation, a contradiction.
The proof is complete.	□
Acknowledgement
The second author is supported by NSFC (No. 11271300) and the Doctorate Foundation of Northwestern Polytechnical University (cx201326).
References
[1]	N. Alon, N. Linial and R. Meshulam, Additive bases of vector spaces over prime fields, J. Combin. Theory Ser. A 57 (1991) 203-210.
[2]	F. Jaeger, Flows and generalized coloring theorems in graphs, J. Combin. Theory Ser. B 26 (1979) 205-216.
[3]	F. Jaeger, N. Linial, C. Payan and M. Tarsi, Group connectivity of graphs-a nonhomogeneous analogue of nowhere-zero flow properties, J. Combin. Theory Ser. B 56 (1992) 165-182.
[4]	M. Kochol, An equivalent version of the 3-flow conjecture, J. Combin. Theory Ser. B 83 (2001) 258-261.
[5]	M. Kochol, Superposition and constructions of graphs without nowhere-zero k-flows, Europ. J. Combin. 23 (2002) 281-306.
[6]	H.-J. Lai and C.-Q. Zhang, Nowhere-zero 3-flows of highly connected graphs, Discrete Math. 110 (1992) 179-183.
[7]	L. M. Lovasz, C. Thomassen, Y.-Z Wu and C.-Q. Zhang, Nowhere-zero 3-flows and modulo k-orientations, J. Combin. Theory Ser. B 103 (2013) 587-598.
[8]	C. Thomassen, The weak 3-flow conjecture, J. Combin. Theory Ser. B 102 (2012) 521-529.
[9]	W. T. Tutte, On the imbedding of linear graphs in surfaces, Proc. London Math. Soc. 51 (1949) 474-483.
[10]	W. T. Tutte, A contribution on the theory of chromatic polynomial, Canad. J. Math. 6 (1954) 80-91.
[11]	C.-Q. Zhang, Integer Flows and Cycle Covers of Graphs, Marcel Dekker Inc., New York, (1997).