Open Problem Garden - Real roots of the flow polynomial - Comments

Not bounded by 5, either (re: Real roots of the flow polynomial)

Robert Samal — Thu, 16 Dec 2010 23:43:53 +0100

A preprint by Jesper L. Jacobsen and Jesus Salas claims that there are graphs with roots of their flow polynomial being above 5. The generalized Petersen graphs G(7n,7) are claimed to have roots of flow polynomial that accumulate at approximately .

I suppose this makes the original conjecture truly false. An interesting variant, though, is to find out, if all roots of flow polynomials are . (Thanks to Bojan Mohar for pointing out the paper to me.)

Welsh's conjecture is false (re: Real roots of the flow polynomial)

Gordon Royle — Fri, 21 Aug 2009 08:27:57 +0200

Welsh's conjecture on flow roots is false. In fact, many cubic graphs with reasonably large girth and enough vertices have flow roots between 4 and 5, and it is almost certain that we can find graphs with flow roots arbitrarily close to 5.

However I strongly believe that "All real roots of nonzero flow polynomials are at most FIVE".

See my recent survey article "Recent results on chromatic and flow roots of graphs and matroids, Surveys in Combinatorics 2009" for more detail.

Gordon Royle

Real roots of the flow polynomial

mdevos — Wed, 07 Mar 2007 11:59:32 +0100

Author(s): Welsh

Subject: Graph Theory » Coloring » Nowhere-zero flows

Conjecture All real roots of nonzero flow polynomials are at most 4.