Tutte's 5-flow conjecture for highly cyclically connected cubic graphs (Q5899393): Difference between revisions

Tutte in 1954 [\textit{W.T. Tutte}, ``A contribution to the theory of chromatic polynomials'', Can. J. Math. 6, 80--91 (1954; Zbl 0055.17101)] conjectured that every bridgeless graph has a nowhere-zero 5-flow. This conjecture is equivalent to its restriction to a cubic graph. Since every bridgeless cubic graph has a 2-factor and the oddness n is the minimum number of odd cycles in a 2-factor of the graph. Therefore, the oddness must be an even number, and that a cubic graph has a nowhere-zero 4-flow if and only if it is edge 3-colorable. The paper shows that if a cubic graph has no edge cut with fewer than \(5n/2 - 3\) edges that separates two odd cycles of a minimum 2-factor of the graph, then the graph has a nowhere-zero 5-flow.