Premium
Tutte's 5‐flow conjecture for graphs of nonorientable genus 5
Author(s) -
Steffen Eckhard
Publication year - 1996
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/(sici)1097-0118(199608)22:4<309::aid-jgt5>3.0.co;2-p
Subject(s) - mathematics , combinatorics , conjecture , multigraph , polyhedral graph , genus , graph , cubic graph , discrete mathematics , chordal graph , 1 planar graph , line graph , botany , voltage graph , biology
We develop four constructions for nowhere‐zero 5‐flows of 3‐regular graphs that satisfy special structural conditions. Using these constructions we show a minimal counter‐example to Tutte's 5‐Flow Conjecture is of order ≥44 and therefore every bridgeless graph of nonorientable genus ≤5 has a nowhere‐zero 5‐flow. One of the structural properties is formulated in terms of the structure of the multigraph G ( F ) obtained from a given 3‐regular graph G by contracting the cycles of a 2‐factor F in G . © 1996 John Wiley & Sons, Inc.