Nowhere-zero 3-flows in Cayley graphs and Sylow 2-subgroups. (English) Zbl 1208.05053

Summary: Tutte’s 3-Flow Conjecture suggests that every bridgeless graph with no 3-edge-cut can have its edges directed and labelled by the numbers 1 or 2 in such a way that at each vertex the sum of incoming values equals the sum of outgoing values. In this paper we show that Tutte’s 3-Flow Conjecture is true for Cayley graphs of groups whose Sylow 2-subgroup is a direct factor of the group; in particular, it is true for Cayley graphs of nilpotent groups. This improves a recent result of P.Potočnik, M. Škoviera and P. Škrekovski [Discrete Math. 297,119-127 (2005)] concerning nowhere-zero 3-flows in abelian Cayley graphs.


05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
20D20 Sylow subgroups, Sylow properties, \(\pi\)-groups, \(\pi\)-structure
Full Text: DOI


[1] Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications. Elsevier, New York (1976) · Zbl 1226.05083
[2] DeVos, M., Xu, R., Yu, G.: Nowhere-zero ℤ3-flows through ℤ3-connectivity. Discrete Math. 306, 26-30 (2006) · Zbl 1086.05043 · doi:10.1016/j.disc.2005.10.019
[3] Diestel, R.: Graph Theory, 3rd edn. Springer, Heidelberg (2005) · Zbl 1074.05001
[4] Gross, J.L., Tucker, T.W.: Topological Graph Theory. Wiley, New York (1987) · Zbl 0621.05013
[5] Grötzsch, H.: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel, Wiss. Zeitschrift d. M.-L.-Universität Halle-Wittenberg. Math.-Naturwiss. Reihe 8, 109-120 (1958/1959)
[6] Imrich, W., Škrekovski, R.: A theorem on integer flows on Cartesian products of graphs. J. Graph. Theory 43, 93-98 (2003) · Zbl 1019.05058 · doi:10.1002/jgt.10100
[7] Jaeger, F.; Beineke, L. W. (ed.); Wilson, R. J. (ed.), Nowhere-zero flow problems, No. 3, 71-95 (1988), London · Zbl 0658.05034
[8] Kochol, M.: An equivalent form of the 3-flow conjecture. J. Combin. Theory Ser. B 83, 258-261 (2001) · Zbl 1029.05088 · doi:10.1006/jctb.2001.2054
[9] Kochol, M.: Equivalence between Hamiltonicity and flow conjectures, and the sublinear defect property. Discrete Math. 254, 221-230 (2002) · Zbl 1063.05083 · doi:10.1016/S0012-365X(01)00372-7
[10] Lai, H.-J.: Nowhere-zero 3-flows in locally connected graphs. J. Graph Theory 42, 211-219 (2003) · Zbl 1015.05037 · doi:10.1002/jgt.10085
[11] Potočnik, P., Škoviera, M., Škrekovski, R.: Nowhere-zero 3-flows in Abelian Cayley Graphs. Discrete Math. 297, 119-127 (2005) · Zbl 1070.05047 · doi:10.1016/j.disc.2005.04.013
[12] Rotman, J.J.: An Introduction to the Theory of Groups, 4th edn. Springer, New York (1999) · Zbl 0810.20001
[13] Shu, J., Zhang, C.-Q.: Nowhere-zero 3-flows in products of graphs. J. Graph Theory 50, 79-89 (2005) · Zbl 1069.05040 · doi:10.1002/jgt.20095
[14] Steinberg, R., Younger, D.: Grötzsch’s theorem for the projective plane. Ars Combin. 28, 15-31 (1989) · Zbl 0721.05025
[15] Sudakov, B.: Nowhere-zero flows in random graphs. J. Combin. Theory Ser. B 81, 209-223 (2001) · Zbl 1027.05086 · doi:10.1006/jctb.2000.2007
[16] Tutte, W.T.: A contribution to the theory of chromatic polynomials. J. Can. Math. Soc. 6, 80-91 (1954) · Zbl 0055.17101
[17] Tutte, W.T.: On the algebraic theory of graph colorings. J. Combin. Theory 1, 15-50 (1966) · Zbl 0139.41402 · doi:10.1016/S0021-9800(66)80004-2
[18] Xu, R., Zhang, C.-Q.: Nowhere-zero 3-flows in squares of graphs. Electronic J. Combin. 10, R5 (2003) · Zbl 1018.05031
[19] Zhang, C.-Q.: Integer Flows and Cycle Covers of Graphs. Dekker, New York (1997)
[20] Zhang, C.-Q.: Circular flows of nearly Eulerian graphs and vertex-splitting. J. Graph Theory 40, 147-151 (2002) · Zbl 1004.05039 · doi:10.1002/jgt.10040
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.