Is the five-flow conjecture almost false?

DOI10.1016/J.JCTB.2013.06.001zbMATH Open1301.05153arXiv1009.4062OpenAlexW2050188822WikidataQ58082143 ScholiaQ58082143MaRDI QIDQ463296FDOQ463296

Jesper Lykke Jacobsen, Jesús Salas

Publication date: 16 October 2014

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

Abstract: The number of nowhere zero Z_Q flows on a graph G can be shown to be a polynomial in Q, defining the flow polynomial Phi_G(Q). According to Tutte's five-flow conjecture, Phi_G(5) > 0 for any bridgeless G.A conjecture by Welsh that Phi_G(Q) has no real roots for Q in (4,infty) was recently disproved by Haggard, Pearce and Royle. These authors conjectured the absence of roots for Q in [5,infty). We study the real roots of Phi_G(Q) for a family of non-planar cubic graphs known as generalised Petersen graphs G(m,k). We show that the modified conjecture on real flow roots is also false, by exhibiting infinitely many real flow roots Q>5 within the class G(nk,k). In particular, we compute explicitly the flow polynomial of G(119,7), showing that it has real roots at Qapprox 5.0000197675 and Qapprox 5.1653424423. We moreover prove that the graph families G(6n,6) and G(7n,7) possess real flow roots that accumulate at Q=5 as n oinfty (in the latter case from above and below); and that Q_c(7)approx 5.2352605291 is an accumulation point of real zeros of the flow polynomials for G(7n,7) as n oinfty.

Full work available at URL: https://arxiv.org/abs/1009.4062

zbMATH Keywords

flow polynomialPetersen graphtransfer matrixnowhere zero flowsflow rootsTutte's five-flow conjecture

Mathematics Subject Classification ID

Flows in graphs (05C21)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Design, analysis, and implementation of a multiprecision polynomial rootfinder
• A Contribution to the Theory of Chromatic Polynomials
• Limits of chromatic zeros of some families of maps
• Every planar map is four colorable. I: Discharging
• The Zero-Free Intervals for Chromatic Polynomials of Graphs
• Flows and generalized coloring theorems in graphs
• A theorem on tait colorings with an application to the generalized Petersen graphs
• Exact Potts model partition functions for strips of the square lattice
• Computing Tutte Polynomials
• Partition algebras.
• Nowhere-zero 6-flows
• Every generalized Petersen graph has a Tait coloring
• On the Imbedding of Linear Graphs in Surfaces
• Limits of zeroes of recursively defined polynomials
• Chromatic Roots are Dense in the Whole Complex Plane
• The largest real zero of the chromatic polynomial
• Phase diagram of the chromatic polynomial on a torus
• Transfer matrices and partition-function zeros for antiferromagnetic Potts models. IV. Chromatic polynomial with cyclic boundary conditions
• A tree-decomposed transfer matrix for computing exact Potts model partition functions for arbitrary graphs, with applications to planar graph colourings
• COLOURING, PACKING AND THE CRITICAL PROBLEM
• Chromatic Polynomials
• Planar triangulations with real chromatic roots arbitrarily close to 4
• The structure of the partition algebras
• Zero-free regions for multivariate tutte polynomials (alias Potts-model partition functions) of graphs and matroids
• Is the four-color conjecture almost false?
• Zeros of chromatic and flow polynomials of graphs
• Potts model and graph theory.
• Restrictions on smallest counterexamples to the 5-flow conjecture
• Tutte's 5-flow conjecture for the projective plane
• The Zero-Free Intervals for Characteristic Polynomials of Matroids
• Combinatorial aspects of boundary loop models
• A generalized Beraha conjecture for non-planar graphs
• A zero-free interval for flow polynomials of cubic graphs
• Character decomposition of Potts model partition functions. I: Cyclic geometry
• Eigenvalue amplitudes of the Potts model on a torus

Cited In (6)

• Density of Real Zeros of the Tutte Polynomial
• A generalized Beraha conjecture for non-planar graphs
• On zeros of the characteristic polynomial of matroids of bounded tree-width
• Transfer matrices and partition-function zeros for antiferromagnetic Potts models. VI. Square lattice with extra-vertex boundary conditions
• Phase diagram of the triangular-lattice Potts antiferromagnet
• On graphs having no flow roots in the interval \((1,2)\)

Uses Software

• OEIS
• na20
• tutte

This page was built for publication: Is the five-flow conjecture almost false?

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