Paper detail

Is the five-flow conjecture almost false?

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 Φ_G(Q). According to Tutte's five-flow conjecture, Φ_G(5) > 0 for any bridgeless G.A conjecture by Welsh that Φ_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 Φ_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 Q\approx 5.0000197675 and Q\approx 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\to\infty (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\to\infty.