5-flow conjecture

Importance: Outstanding ✭✭✭✭
Author(s): Tutte, William T.
Recomm. for undergrads: no
Prize: none
Posted by: mdevos
on: March 7th, 2007

\begin{conjecture} Every \Def[bridgeless]{bridge (graph theory)} graph has a \Def[nowhere-zero]{nowhere-zero flows} 5-flow. \end{conjecture}

For \Def{planar graphs}, this theorem follows from \Def[flow/coloring duality]{nowhere-zero flows}, and the \Def{Five color theorem} (every loopless planar graph is 5-colorable). In light of this, we may view this conjecture as a widesweeping generalization of the 5-color-theorem. The \Def{Petersen graph} does not have a nowhere-zero 4-flow, which shows that this conjecture (if true) is best possible.

It is far from obvious that there should exist a fixed number $k$ so that every bridgeless graph has a nowhere-zero $k$-flow. Indeed, this weaker conjecture was also made by Tutte, but was resolved by Kilpatrick [K] and independently Jaeger [J], who both proved that bridgeless graphs have nowhere-zero 8-flows. Seymour [S] improved upon this result by showing that bridgeless graphs have nowhere-zero 6-flows.


[J] F. Jaeger, Flows and Generalized Coloring Theorems in Graphs, J. Combinatorial Theory Ser. B 26 (1979) 205-216. \MRhref{0532588}

[K] P.A. Kilpatrick, Tutte's First Colour-Cycle Conjecture, Thesis, Cape Town (1975).

[S] P.D. Seymour, Nowhere-Zero 6-Flows, J. Combinatorial Theory Ser. B 30 (1981) 130-135. \MRhref{0615308}

[T54] W.T. Tutte, A Contribution on the Theory of Chromatic Polynomials, Canad. J. Math. 6 (1954) 80-91. \MRhref{0061366}

[Tt66] W.T. Tutte, On the Algebraic Theory of Graph Colorings, J. Combinatorial Theory 1 (1966) 15-50. \MRhref{0194363}

* indicates original appearance(s) of problem.