Premium
Nowhere‐zero flows in low genus graphs
Author(s) -
Möller Martina,
Carstens Hans Georg,
Brinkmann Gunnar
Publication year - 1988
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190120208
Subject(s) - mathematics , combinatorics , polyhedral graph , genus , planar graph , conjecture , discrete mathematics , chordal graph , counterexample , 1 planar graph , graph , botany , biology
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.