Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649485 | Discrete Mathematics | 2010 | 5 Pages |
Abstract
In 1954, Tutte conjectured that every bridgeless graph has a nowhere-zero 5-flow. Let ω(G)ω(G) be the minimum number of odd cycles in a 2-factor of a bridgeless cubic graph GG. Tutte’s conjecture is equivalent to its restriction to cubic graphs with ω≥2ω≥2. We show that if a cubic graph GG has no edge cut with fewer than 52ω(G)−3 edges that separates two odd cycles of a minimum 2-factor of GG, then GG has a nowhere-zero 5-flow. This implies that if a cubic graph GG is cyclically nn-edge connected and n≥52ω(G)−3, then GG has a nowhere-zero 5-flow.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Eckhard Steffen,