Nowhere-zero flows

Open problems about Nowhere-zero flows (not to be confused with Network flows).

Graph Theory » Coloring » Nowhere-zero flows

5-flow conjecture ★★★★

Author(s): Tutte

Conjecture Every bridgeless graph has a nowhere-zero 5-flow.

Keywords: cubic; nowhere-zero flow

Posted by mdevos
updated March 7th, 2007

add new comment

Graph Theory » Coloring » Nowhere-zero flows

4-flow conjecture ★★★

Author(s): Tutte

Conjecture Every bridgeless graph with no Petersen minor has a nowhere-zero 4-flow.

Keywords: minor; nowhere-zero flow; Petersen graph

Posted by mdevos
updated April 12th, 2009

2 comments

Graph Theory » Coloring » Nowhere-zero flows

3-flow conjecture ★★★

Author(s): Tutte

Conjecture Every 4-edge-connected graph has a nowhere-zero 3-flow.

Keywords: nowhere-zero flow

Posted by mdevos
updated April 12th, 2011

1 comment

Graph Theory » Coloring » Nowhere-zero flows

Jaeger's modular orientation conjecture ★★★

Author(s): Jaeger

Conjecture Every $4k$ -edge-connected graph can be oriented so that ${\mathit indegree}(v) - {\mathit outdegree}(v) \cong 0$ (mod $2k+1$ ) for every vertex $v$ .

Keywords: nowhere-zero flow; orientation

Posted by mdevos
updated March 7th, 2007

add new comment

Graph Theory » Coloring » Nowhere-zero flows

Bouchet's 6-flow conjecture ★★★

Author(s): Bouchet

Conjecture Every bidirected graph with a nowhere-zero $k$ -flow for some $k$ , has a nowhere-zero $6$ -flow.

Keywords: bidirected graph; nowhere-zero flow

Posted by mdevos
updated March 7th, 2007

add new comment | 1 attachment

Graph Theory » Coloring » Nowhere-zero flows

The three 4-flows conjecture ★★

Author(s): DeVos

Conjecture For every graph $G$ with no bridge, 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 nowhere-zero 4-flow for $1 \le i \le 3$ .

Keywords: nowhere-zero flow

Posted by mdevos
updated March 7th, 2007

add new comment

Graph Theory » Coloring » Nowhere-zero flows

A homomorphism problem for flows ★★

Author(s): DeVos

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 homomorphism from $Cayley(M,B)$ to $Cayley(M',B')$ , then every graph with a B-flow has a B'-flow.

Keywords: homomorphism; nowhere-zero flow; tension

Posted by mdevos
updated March 7th, 2007

add new comment

Graph Theory » Coloring » Nowhere-zero flows

Real roots of the flow polynomial ★★

Author(s): Welsh

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

Keywords: flow polynomial; nowhere-zero flow

Posted by mdevos
updated December 17th, 2010

2 comments

Graph Theory » Coloring » Nowhere-zero flows

Unit vector flows ★★

Author(s): Jain

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

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.

Keywords: nowhere-zero flow

Posted by mdevos
updated March 7th, 2007

add new comment

Graph Theory » Coloring » Nowhere-zero flows

Antichains in the cycle continuous order ★★

Author(s): DeVos

If $G$ , $H$ are graphs, a function $f : E(G) \rightarrow E(H)$ is called 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$ .

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$ ?

Keywords: antichain; cycle; poset

Posted by mdevos
updated May 12th, 2007

add new comment

Graph Theory » Coloring » Nowhere-zero flows

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)$ .