Is the five-flow conjecture almost false?

DOI10.1016/J.JCTB.2013.06.001MaRDI QIDQ463296zbMATH OpenOpenAlexWikidataFDO

Authors Jesper Lykke Jacobsen, Jesús Salas

Publication date 16 October 2014

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

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)

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.

Recommendations

• On zero-free intervals of flow polynomials
• On graphs whose flow polynomials have real roots only
• Nowhere-zero 5-flows on cubic graphs with oddness 4
• Tutte's 5-flow conjecture for the projective plane
• A survey on the study of real zeros of flow polynomials

Cites work

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

Cited in

(6)

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

Describes a project that uses

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)