Originator(s): William Tutte
Conjecture/Question: Every bridgeless graph has a nowhere-zero 5-flow.
Definitions/Background/motivation: A bridgeless graph is a graph with no cut-edge. For planar graphs, the conjecture is equivalent to the statement that all planar graphs are 5-colorable, so the conjecture generalizes that statement.
Comments/Partial results: Kilpatrick [K] and Jaeger [J] proved that every bridgeless graph is 8-flowable. Seymour [Se] proved that every bridgeless graph is 6-flowable.
Celmins proved that a smallest counterexample to 5-flowability must be a cyclically 5-edge-connected snark with girth at least 7. Steinberg [St] proved the conjecture for graphs embeddable in the projective plane.
The conjecture is implied by a conjecture of Archdeacon [1984] and Jaeger [1988] that bridgeless graphs have orientable cycle double covers of order at most 5.
References:
[Se] Seymour, P. D. Nowhere-zero $6$-flows. J. Combin. Theory Ser. B 30 (1981),
no. 2, 130--135.
[St] Steinberg, Richard Tutte's $5$-flow conjecture for the projective plane.
J. Graph Theory 8 (1984), no. 2, 277--289.
Keywords: