Smallest counterexample to the 5-flow conjecture has girth at least eleven

DOI10.1016/J.JCTB.2009.12.001MaRDI QIDQ974466zbMATH OpenOpenAlexFDO

Authors Martin Kochol

Publication date 3 June 2010

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jctb.2009.12.001

zbMATH Keywords

girthnowhere-zero 5-flowpermutation grouprank of a matrix

Mathematics Subject Classification ID

Flows in graphs (05C21) Graph theory (05C99)

Review text

A graph admits a nowhere-zero k-flow if its edges can be oriented and assigned numbers so that for every vertex, the sum of the values on incoming edges equals the sum on the outgoing ones. The famous 5-flow conjecture of Tutte is that every bridgeless graph has a nowhere-zero 5-flow. The paper shows that a smallest counterexample to this conjecture must have girth at least 11.

Recommendations

• About Counterexamples to The 5-Flow Conjecture
• Nowhere-zero 5-flows on cubic graphs with oddness 4
• Tutte's 5-flow conjecture for graphs of nonorientable genus 5
• Nowhere-zero 5-flows
• Tutte's 5-flow conjecture for the projective plane

Cites work

• A Class Of Abelian Groups
• A Contribution to the Theory of Chromatic Polynomials
• A cyclically 6-edge-connected snark of order 118
• Counting nowhere-zero flows on wheels
• Decomposition formulas for the flow polynomial
• scientific article; zbMATH DE number 4006288 (Why is no real title available?)
• scientific article; zbMATH DE number 4075098 (Why is no real title available?)
• Infinite Families of Nontrivial Trivalent Graphs Which are Not Tait Colorable
• Matrix reduction in a combinatorial computation
• Reduction of the 5-flow conjecture to cyclically 6-edge-connected snarks.
• Restrictions on smallest counterexamples to the 5-flow conjecture
• Snarks without small cycles
• Superposition and constructions of graphs without nowhere-zero k-flows

Cited in

(11)

• Matrix reduction in a combinatorial computation
• The Chvátal-Erdős condition for group connectivity in graphs
• Reductions of matrices associated with nowhere-zero flows
• Nowhere-zero 5-flows
• About Counterexamples to The 5-Flow Conjecture
• Flow-Critical Graphs
• Reduction of the Berge-Fulkerson conjecture to cyclically 5-edge-connected snarks
• Nowhere-zero 5-flows on cubic graphs with oddness 4
• Avoiding 5-Circuits in 2-Factors of Cubic Graphs
• Measures of edge-uncolorability of cubic graphs
• Counting nowhere-zero flows on wheels

This page was built for publication: Smallest counterexample to the 5-flow conjecture has girth at least eleven

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q974466)