Half-integral flow polynomial values

Importance: Medium ✭✭
Author(s): Mohar, Bojan
Keywords: nowhere-zero flow
Recomm. for undergrads: no
Posted by: mohar
on: May 31st, 2007

Let $\Phi(G,x)$ be the flow polynomial of a graph $G$. So for every positive integer $k$, the value $\Phi(G,k)$ equals the number of \Def[nowhere-zero]{nowhere-zero flows} $k$-flows in $G$.

\begin{conjecture} $\Phi(G,5.5) > 0$ for every 2-edge-connected graph $G$. \end{conjecture}

By Seymour's 6-flow theorem, $\Phi(G,k) > 0$ for every 2-edge-connected graph $G$ and every integer $k\ge6$.

It would be interesting to find any non-integer rational number $x>5$ so that $\Phi(G,x) > 0$ for every 2-edge-connected graph $G$. It is known that zeros of flow polynomials are dense in the complex plane.


% Example: %*[B] Claude Berge, Farbung von Graphen, deren samtliche bzw. deren ungerade Kreise starr sind, Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe 10 (1961), 114. % %[CRS] Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas: \arxiv[The strong perfect graph theorem]{math.CO/0212070}, % Ann. of Math. (2) 164 (2006), no. 1, 51--229. \MRhref{MR2233847} % % (Put an empty line between individual entries)

* indicates original appearance(s) of problem.