Journal of Graph Theory · 1988 · 11 citations · 5 references
Natural SciencesComputer ScienceMathematicsCombinatoricsGeometryTopologyDirected Acyclic GraphsGraph TheoryTopological CombinatoricsTopological Graph Theory
Abstract A nowhere‐zero k ‐flow is an assignment of edge directions and integer weights in the range 1,…, k − 1 to the edges of an undirected graph such that at every vertex the flow in is equal to the flow out. Tutte has conjectured that every bridgeless graph has a nowhere‐zero 5‐flow. We show that a counterexample to this conjecture, minimal in the class of graphs embedded in a surface of fixed genus, has no face‐boundary of length <7. Moreover, in order to prove or disprove Tutte's conjecture for graphs of fixed genus γ, one has to check graphs of order at most 28(γ − 1) in the orientable case and 14(γ − 2) in the nonorientable case. So, in particular, it follows immediately that every bridgeless graph of orientable genus ⩽1 or nonorientable genus ⩽2 has a nowhere‐zero 5‐flow. Using a computer, we checked that all graphs of orientable genus ⩽2 or nonorientable genus ⩽4 have a nowhere‐zero 5‐flow.
5
D. H. Younger · Journal of Graph Theory · 1983 · 38 citations
Tutte's 5‐flow conjecture for the projective plane
Richard Steinberg · Journal of Graph Theory · 1984 · 10 citations