Smallest counterexample to the 5-flow conjecture has girth at least eleven. (English) Zbl 1211.05055

A graph admits a nowhere-zero k-flow if its edges can be oriented and assigned numbers so that for every vertex, the sum of the values on incoming edges equals the sum on the outgoing ones. The famous 5-flow conjecture of Tutte is that every bridgeless graph has a nowhere-zero 5-flow. The paper shows that a smallest counterexample to this conjecture must have girth at least 11.


05C21 Flows in graphs
05C99 Graph theory
Full Text: DOI


[1] Gross, J. L.; Tuker, T. W., Topological Graph Theory (1987), Wiley: Wiley New York · Zbl 0621.05013
[2] Isaacs, R., Infinite families of nontrivial trivalent graphs which are not Tait colorable, Amer. Math. Monthly, 82, 221-239 (1975) · Zbl 0311.05109
[3] Jaeger, F., Nowhere-zero flow problems, (Beineke, L. W.; Wilson, R. J., Selected Topics in Graph Theory, vol. 3 (1988), Academic Press: Academic Press New York), 71-95 · Zbl 0658.05034
[4] Kochol, M., Snarks without small cycles, J. Combin. Theory Ser. B, 67, 34-47 (1996) · Zbl 0855.05066
[5] Kochol, M., A cyclically 6-edge-connected snark of order 118, Discrete Math., 161, 297-300 (1996) · Zbl 0870.05025
[6] Kochol, M., Superposition and constructions of graphs without nowhere-zero \(k\)-flows, European J. Combin., 23, 281-306 (2002) · Zbl 1010.05062
[7] Kochol, M., Reduction of the 5-flow conjecture to cyclically 6-edge-connected snarks, J. Combin. Theory Ser. B, 90, 139-145 (2004) · Zbl 1033.05067
[8] Kochol, M., Decomposition formulas for the flow polynomial, European J. Combin., 26, 1086-1093 (2005) · Zbl 1076.05080
[9] Kochol, M., Restrictions on smallest counterexamples to the 5-flow conjecture, Combinatorica, 26, 83-89 (2006) · Zbl 1100.05034
[10] Kochol, M.; Krivoňáková, N.; Smejová, S.; Šranková, K., Counting nowhere-zero flows on wheels, Discrete Math., 308, 2050-2053 (2008) · Zbl 1148.05033
[11] M. Kochol, N. KrivoňÁková, S. Smejová, K. Šranková, Matrix reduction in a combinatorial computation, manuscript; M. Kochol, N. KrivoňÁková, S. Smejová, K. Šranková, Matrix reduction in a combinatorial computation, manuscript · Zbl 1259.05072
[12] Tutte, W. T., A contribution to the theory of chromatic polynomials, Canad. J. Math., 6, 80-91 (1954) · Zbl 0055.17101
[13] Tutte, W. T., A class of Abelian groups, Canad. J. Math., 8, 13-28 (1956) · Zbl 0070.02302
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.