## Can the flow polynomial have large (real) zeros?

The well-known ** 5-Flow Conjecture** of Tutte states that

**Conjecture 1 (Tutte [2]):**
If G is a 2-edge-connected graph, then G admits a
nowhere-zero 5-flow.

If true, Conjecture 1 would imply that for every integer *k* > 4, the flow polynomial of any 2-edge-connected graph has a nonzero value at *k*.
(This is known to be true for integers greater than 5 by Seymour's 6-Flow Theorem [1].)

**Conjecture 2 (Welsh):**
Let G be a 2-edge-connected graph and let F(G, *x*)
denote its flow polynomial. Then for every *x* > 4, F(G, *x*) >
0.

There are two known facts which make this conjecture quite surprising. For
the dual concept - the chromatic polynomial of a graph - there are known
examples of 3-colorable graphs whose chromatic polynomials have arbitrarily
large zeros. Secondly, it is known that the set of roots of flow polynomials is
dense in the complex plane.

References:

[1] P.D. Seymour, Nowhere-zero 6-flows,
J. Combin. Theory Ser. B 30 (1981) 130-135.

[2] W.T. Tutte, A contribution to the theory of chromatic polynomials,**
**Canad. J. Math. 6 (1954) 80-91.

Send comments to Bojan.Mohar@uni-lj.si

##### Revised: april 07, 2003.