pith. sign in

arxiv: math/0607077 · v2 · pith:LHJSVINQnew · submitted 2006-07-04 · 🧮 math.CO

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

classification 🧮 math.CO
keywords cubicflowgraphomeganowhere-zerotuttebridgelessconjecture
0
0 comments X
read the original 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 \geq 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 \geq {5/2} \omega - 1$, then $G$ has a nowhere-zero 5-flow.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.