5-flow conjecture
Status partial high confidence
Tutte's 5-flow conjecture remains open; Seymour's 1981 result (every bridgeless graph has a nowhere-zero 6-flow) is still the best universal bound. Since the OPG posting, partial progress has been made extending the conjecture to special classes of cubic graphs: cyclically 6-edge-connected cubic graphs satisfying certain conditions on 1-factor intersections (Steffen 2015), and cyclically 6-edge-connected cubic graphs with oddness at most 4 (Mazzuoccolo–Steffen 2017).
Cited literature (2)
-
Proves that a cyclically $n$-edge-connected cubic graph has a nowhere-zero 5-flow if either ($n\ge 6$ and $\mu_2(G)\le 2$) or $n\ge 5\mu_2(G)-3$, where $\mu_2(G)$ is the minimum size of the intersection of two 1-factors.
-
Proves that every cyclically 6-edge-connected cubic graph with oddness at most 4 has a nowhere-zero 5-flow, extending the conjecture's verification to a broader class of potential snarks.
Reviewer notes. The Steffen (2010) paper 'Tutte's 5-Flow Conjecture for Highly Cyclically Connected Cubic Graphs' (Discrete Math. 310, 385-389) was on arXiv in July 2006 (before the OPG posting date) and is excluded from since_posted as its content predated the posting, even though the journal publication appeared in 2010. The DOI 10.1002/jgt.22065 for the Mazzuoccolo–Steffen paper was found in search results (Wiley URL) but the journal page returned 403; the arXiv abstract page (fetched successfully) confirmed title, authors, and main theorem. The withdrawn Mkrtchyan (2020) paper arXiv:2008.07152 was found to duplicate earlier work and is not cited. No post-2017 result extending oddness beyond 4 or resolving the conjecture in a wider class was found. Seymour's 6-flow theorem from 1981 remains the best universal result.
Discussion
For planar graphs , this theorem follows from flow/coloring duality , and the Five color theorem (every loopless planar graph is 5-colorable). In light of this, we may view this conjecture as a widesweeping generalization of the 5-color-theorem. The Petersen graph does not have a nowhere-zero 4-flow, which shows that this conjecture (if true) is best possible. It is far from obvious that there should exist a fixed number $ k $ so that every bridgeless graph has a nowhere-zero $ k $ -flow. Indeed, this weaker conjecture was also made by Tutte, but was resolved by Kilpatrick [K] and independently Jaeger [J], who both proved that bridgeless graphs have nowhere-zero 8-flows. Seymour [S] improved upon this result by showing that bridgeless graphs have nowhere-zero 6-flows.
Bibliography
-
[J]F. Jaeger, Flows and Generalized Coloring Theorems in Graphs, J. Combinatorial Theory Ser. B 26 (1979) 205-216. MathSciNet MathSciNet -
[K]P.A. Kilpatrick, Tutte's First Colour-Cycle Conjecture, Thesis, Cape Town (1975). -
[S]P.D. Seymour, Nowhere-Zero 6-Flows, J. Combinatorial Theory Ser. B 30 (1981) 130-135. MathSciNet MathSciNet -
[T54]W.T. Tutte, A Contribution on the Theory of Chromatic Polynomials, Canad. J. Math. 6 (1954) 80-91. MathSciNet MathSciNet -
[Tt66]W.T. Tutte, On the Algebraic Theory of Graph Colorings, J. Combinatorial Theory 1 (1966) 15-50. MathSciNet MathSciNet