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