Tutte's 5-Flow Conjecture for Highly Cyclically Connected Cubic Graphs

Abstract

In 1954, Tutte conjectured that every bridgeless graph has a nowhere-zero 5-flow. Let $\omega$ be the minimum number of odd cycles in a 2-factor of a bridgeless cubic graph. Tutte's conjecture is equivalent to its restriction to cubic graphs with $\omega \ge 2$. We show that if a cubic graph $G$ has no edge cut with fewer than $5/2\omega -1$ edges that separates two odd cycles of a minimum 2-factor of $G$, then $G$ has a nowhere-zero 5-flow. This implies that if a cubic graph $G$ is cyclically $n$-edge connected and $n\ge 5/2\omega -1$, then $G$ has a nowhere-zero 5-flow.

Cited by in corpus (4)

• Flows and bisections in cubic graphs
• Intersecting 1-factors and nowhere-zero 5-flows
• Measures of edge-uncolorability
• A survey on the study of real zeros of flow polynomials