Nowhere-zero flows

Open problems about \Def{Nowhere-zero flows} (not to be confused with \Def[Network flows]{Flow_network}).



5-flow conjecture ★★★★

Author(s): Tutte

\begin{conjecture} Every \Def[bridgeless]{bridge (graph theory)} graph has a \Def[nowhere-zero]{nowhere-zero flows} 5-flow. \end{conjecture}

Keywords: cubic; nowhere-zero flow

4-flow conjecture ★★★

Author(s): Tutte

\begin{conjecture} Every \Def[bridgeless]{bridge (graph theory)} graph with no \Def[Petersen]{petersen graph} \Def[minor]{minor (graph theory)} has a \Def[nowhere-zero]{nowhere-zero flows} 4-flow. \end{conjecture}

Keywords: minor; nowhere-zero flow; Petersen graph

3-flow conjecture ★★★

Author(s): Tutte

\begin{conjecture} Every 4-\Def[edge-connected]{connectivity (graph theory)} graph has a \Def[nowhere-zero]{nowhere-zero flows} 3-flow. \end{conjecture}

Keywords: nowhere-zero flow

Jaeger's modular orientation conjecture ★★★

Author(s): Jaeger

\begin{conjecture} Every $4k$-\Def[edge-connected]{connectivity (graph theory)} graph can be oriented so that ${\mathit indegree}(v) - {\mathit outdegree}(v) \cong 0$ (mod $2k+1$) for every vertex $v$. \end{conjecture}

Keywords: nowhere-zero flow; orientation

Bouchet's 6-flow conjecture ★★★

Author(s): Bouchet

\begin{conjecture} Every bidirected graph with a nowhere-zero $k$-flow for some $k$, has a nowhere-zero $6$-flow. \end{conjecture}

Keywords: bidirected graph; nowhere-zero flow

The three 4-flows conjecture ★★

Author(s): DeVos

\begin{conjecture} For every graph $G$ with no \Def[bridge]{bridge (graph theory)}, there exist three disjoint sets $A_1,A_2,A_3 \subseteq E(G)$ with $A_1 \cup A_2 \cup A_3 = E(G)$ so that $G \setminus A_i$ has a \Def[nowhere-zero]{nowhere-zero flows} 4-flow for $1 \le i \le 3$. \end{conjecture}

Keywords: nowhere-zero flow

A homomorphism problem for flows ★★

Author(s): DeVos

\begin{conjecture} Let $M,M'$ be abelian groups and let $B \subseteq M$ and $B' \subseteq M'$ satisfy $B=-B$ and $B' = -B'$. If there is a \Def[homomorphism]{graph homomorphism} from $Cayley(M,B)$ to $Cayley(M',B')$, then every graph with a B-flow has a B'-flow. \end{conjecture}

Keywords: homomorphism; nowhere-zero flow; tension

Real roots of the flow polynomial ★★

Author(s): Welsh

\begin{conjecture} All real roots of nonzero flow polynomials are at most 4. \end{conjecture}

Keywords: flow polynomial; nowhere-zero flow

Unit vector flows ★★

Author(s): Jain

\begin{conjecture} For every graph $G$ without a \Def[bridge]{bridge (graph theory)}, there is a flow $\phi : E(G) \rightarrow S^2 = \{ x \in {\mathbb R}^3 : |x| = 1 \}$.

\end{conjecture}

\begin{conjecture} There exists a map $q:S^2 \rightarrow \{-4,-3,-2,-1,1,2,3,4\}$ so that antipodal points of $S^2$ receive opposite values, and so that any three points which are equidistant on a great circle have values which sum to zero. \end{conjecture}

Keywords: nowhere-zero flow

Antichains in the cycle continuous order ★★

Author(s): DeVos

If $G$,$H$ are graphs, a function $f : E(G) \rightarrow E(H)$ is called \emph{cycle-continuous} if the pre-image of every element of the (binary) cycle space of $H$ is a member of the cycle space of $G$.

\begin{problem} Does there exist an infinite set of graphs $\{G_1,G_2,\ldots \}$ so that there is no cycle continuous mapping between $G_i$ and $G_j$ whenever $i \neq j$ ? \end{problem}

Keywords: antichain; cycle; poset

Circular flow number of regular class 1 graphs ★★

Author(s): Steffen

A nowhere-zero $r$-flow $(D(G),\phi)$ on $G$ is an orientation $D$ of $G$ together with a function $\phi$ from the edge set of $G$ into the real numbers such that $1 \leq |\phi(e)| \leq r-1$, for all $e \in E(G)$, and $\sum_{e \in E^+(v)}\phi(e) = \sum_{e \in E^-(v)}\phi(e), \textrm{ for all } v \in V(G)$. The circular flow number of $G$ is inf$\{ r | G$ has a nowhere-zero $r$-flow $\}$, and it is denoted by $F_c(G)$.

A graph with maximum vertex degree $k$ is a class 1 graph if its edge chromatic number is $k$.

\begin{conjecture} Let $t \geq 1$ be an integer and $G$ a $(2t+1)$-regular graph. If $G$ is a class 1 graph, then $F_c(G) \leq 2 + \frac{2}{t}$. \end{conjecture}

Keywords: nowhere-zero flow, edge-colorings, regular graphs


Syndicate content