Boundedness of the real flow roots of bridgeless graphs (Jacobsen–Salas Conjecture 1.9: $\Phi_G(Q)>0$ for $Q \ge 6$)

The flow polynomial $\Phi_G(Q)$ of a bridgeless graph $G$ counts nowhere-zero $Q$-flows and is the planar dual of the chromatic polynomial. Tutte's five-flow conjecture asserts $\Phi_G(5)>0$ for every bridgeless graph; Welsh's stronger real-valued conjecture ($\Phi_G(Q)>0$ for real $Q>4$) and the Haggard–Pearce–Royle modification ($Q \ge 5$) were both refuted, the latter by Jacobsen and Salas, who showed that real flow roots accumulate at $Q=5$ from both sides, reach $Q \approx 5.1653424423$, and accumulate at $Q_c(7) \approx 5.2352605291$. The problem this leaves open is to determine the upper end of the real flow-root spectrum of bridgeless graphs — in particular, to prove or refute Jacobsen–Salas's Conjecture 1.9 that $\Phi_G(Q)>0$ for all bridgeless $G$ and all real $Q \ge 6$; more generally, to decide whether any finite uniform upper bound for real flow roots exists, or whether real flow roots are unbounded. A 2019 survey by Dong and the 2018 Tutte-polynomial zero-density results of Ok and Perrett record the question as the outstanding open problem on the upper end of the real flow-root spectrum, and it remains untouched by adjacent 2024–2026 work.

Background

A nowhere-zero $Q$-flow on a graph $G$ is an orientation of its edges together with an assignment of nonzero values from an Abelian group of order $Q$ to the edges so that flow is conserved at every vertex (Kirchhoff's law). The number of such flows is a polynomial in $Q$, the flow polynomial $\Phi_G(Q)$, introduced by Tutte; it vanishes identically exactly when $G$ has a bridge (an edge whose deletion disconnects the graph), so flow theory concerns bridgeless (finite undirected, possibly with loops and parallel edges) graphs. For a connected plane graph $G$ with planar dual $G^*$, Tutte duality gives $P_G(Q) = Q\,\Phi_{G^*}(Q)$, where $P_G$ is the chromatic polynomial (the polynomial counting proper vertex-colourings of $G$ with $Q$ colours); thus chromatic roots of planar graphs are flow roots of their duals, and problems about colouring planar graphs translate into problems about flows on arbitrary bridgeless graphs. This is the source of a suggestive dictionary: the four-colour theorem ($P_G(4)>0$ for planar $G$) corresponds to Tutte's five-flow conjecture (1954), that $\Phi_G(5)>0$ for every bridgeless $G$, still open; the best general result is Seymour's theorem that every bridgeless graph admits a nowhere-zero 6-flow, i.e. $\Phi_G(Q)>0$ for all integers $Q \ge 6$. Kochol proved that a smallest counterexample to the five-flow conjecture must have girth at least 9 (girth being the length of a shortest cycle), so candidate graphs are necessarily large and sparse.

The real-valued analog of these statements has a rocky history. Welsh conjectured $\Phi_G(Q)>0$ for all real $Q \in (4,\infty)$, by analogy with the (still open) Birkhoff–Lewis conjecture that $P_G(Q)>0$ for planar $G$ and real $Q \ge 4$. Haggard, Pearce and Royle refuted Welsh's conjecture: the generalized Petersen graph $G(16,6)$ has real flow roots near $4.0252205$ and $4.2331455$ (the generalized Petersen graph $G(m,k)$ has vertices $u_i, v_i$ with spokes $u_iv_i$, outer cycle edges $u_iu_{i+1}$, and inner edges $v_iv_{i+k}$). The same authors conjectured the modification $\Phi_G(Q)>0$ for real $Q \in [5,\infty)$. Jacobsen and Salas then refuted this too: by an exact transfer-matrix computation (a finite-state dynamic-programming technique that exploits the repeated circular structure of the family) of the flow polynomials of the graphs $G(nk,k)$, they proved that $Q=5$ is an accumulation point of real flow zeros approached from both below and above within the families $G(6n,6)$ and $G(7n,7)$, exhibited the explicit root $Q \approx 5.1653424423$ of $\Phi_{G(119,7)}(Q)$ (the largest real flow root computed in the literature), and proved that $Q_c(7) \approx 5.2352605291$ (where $Q_c(k)$ denotes the largest real point where the limiting curves of zeros of $\Phi_{G(nk,k)}(Q)$ cross the real axis as $n \to \infty$) is an accumulation point of real zeros. In the sense of Beraha–Kahane–Weiss's classic paper on chromatic roots accumulating at $Q=4$, the five-flow conjecture is thus 'almost false': real roots crowd arbitrarily close to $Q=5$ (and slightly beyond it), even though no integer-valued obstruction at $Q=5$ is known.

What survives at the upper end is precisely the open problem. Only a per-graph bound is known: Jackson proved that every real flow root of a bridgeless graph of order $n$ is smaller than $2\log_2 n$ (a special case of a matroidal result on the characteristic polynomial), which grows with $n$ and yields no uniform bound. Jacobsen and Salas computed $Q_c(k)$ for $k \le 11$ and observed a numerical extrapolation $\lim_{k\to\infty} Q_c(k) \approx 5.69$, suggesting the generalized Petersen family may harbor accumulation points beyond $Q_c(7)$; however, their eigenvalue analysis (their Lemma 4.3, a distinctness and no-degenerate-dominance property of the transfer-matrix eigenvalues) is proved only for $k \le 7$, by explicit computation, and its extension to $k \ge 8$ is conjectural. Finally, the question has an external calibration point: Ok and Perrett proved that real zeros of the two-variable Tutte polynomial (the common generalization of the chromatic and flow polynomials, with the flow polynomial sitting on the line $v=-q$) are dense in large regions of the plane, confirming a conjecture of Jackson and Sokal in all regions except $q>4$, $v<-q$ — the one region whose resolution is blocked exactly by the unknown boundedness of real flow roots.

Problem Statement

Determine the upper end of the real flow-root spectrum of bridgeless graphs. Concretely, with $\Phi_G(Q)$ the flow polynomial of a bridgeless graph $G$ (finite undirected multigraphs, loops and parallel edges allowed, as is standard):

1. Prove or refute Conjecture 1.9 of Jacobsen–Salas: $\Phi_G(Q) > 0$ for every bridgeless graph $G$ and every real $Q \ge 6$. A refutation consists of an explicit bridgeless graph with a certified real flow root at or above $6$.
2. More generally, decide whether there exists any finite uniform upper bound $c$ such that $\Phi_G(Q) > 0$ for all bridgeless $G$ and all real $Q \ge c$ (Dong's weaker conjecture), or whether instead the real flow roots of bridgeless graphs are unbounded.
3. Locate the spectrum between the largest known accumulation point $Q_c(7) \approx 5.2352605291$ and the conjectured threshold: determine whether real flow roots strictly between $Q_c(7)$ and $6$ exist.

These items all bear on one objective — computing or bounding $\sup\{Q \in \mathbb{R} : \Phi_G(Q) = 0 \text{ for some bridgeless } G\}$, a quantity known to lie in $[Q_c(7), \infty]$ because real zeros accumulate at $Q_c(7) \approx 5.2352605291$. Item 1 is the case $c = 6$ of the uniform-bound question in item 2; a refutation of item 1 — an explicit bridgeless graph with a certified real flow root at or above $6$ — establishes the lower bound $\sup \ge 6$. The integer statement $\Phi_G(5) > 0$ (Tutte's five-flow conjecture) is the separate famous open problem that motivates this question.

References

1. Jesper Lykke Jacobsen and Jesús Salas, "Is the five-flow conjecture almost false?", Journal of Combinatorial Theory, Series B 103 (2013) 532–565. DOI: 10.1016/j.jctb.2013.06.001; arXiv:1009.4062. https://doi.org/10.1016/j.jctb.2013.06.001
2. Fengming Dong, "A survey on the study of real zeros of flow polynomials", Journal of Graph Theory 92 (2019) 361–376. DOI: 10.1002/jgt.22458; arXiv:2007.05195. https://doi.org/10.1002/jgt.22458
3. Seongmin Ok and Thomas J. Perrett, "Density of Real Zeros of the Tutte Polynomial", Combinatorics, Probability and Computing 27 (2018) 398–410. DOI: 10.1017/S0963548318000019; arXiv:1608.08747. https://doi.org/10.1017/S0963548318000019
4. Jesper Lykke Jacobsen and Jesús Salas, "A generalized Beraha conjecture for non-planar graphs", Nuclear Physics B 875 (2013) 678–718. DOI: 10.1016/j.nuclphysb.2013.07.012. https://doi.org/10.1016/j.nuclphysb.2013.07.012
5. Gary Haggard, David J. Pearce, and Gordon Royle, "Computing Tutte Polynomials", ACM Transactions on Mathematical Software 37 (2010), article 24, 1–17. DOI: 10.1145/1824801.1824802. https://doi.org/10.1145/1824801.1824802
6. P. D. Seymour, "Nowhere-zero 6-flows", Journal of Combinatorial Theory, Series B 30 (1981) 130–135. DOI: 10.1016/0095-8956(81)90058-7. https://doi.org/10.1016/0095-8956(81)90058-7
7. Bill Jackson, "Zeros of chromatic and flow polynomials of graphs", Journal of Geometry 76 (2003) 95–109. DOI: 10.1007/s00022-003-1694-y. https://doi.org/10.1007/s00022-003-1694-y
8. Martin Kochol, "Restrictions on smallest counterexamples to the 5-flow conjecture", Combinatorica 26 (2006) 83–89. DOI: 10.1007/s00493-006-0006-1. https://doi.org/10.1007/s00493-006-0006-1
9. Meiqiao Zhang and Fengming Dong, "Real-rooted flow polynomials have only integer roots", arXiv:2608.19780 (2026). https://arxiv.org/abs/2608.19780
10. Tingzeng Wu, Shuang Ma, and Hong-Jian Lai, "Improved bounds for the coefficient of flow polynomials", arXiv:2502.12773 (2025). https://arxiv.org/abs/2502.12773