nowhere-zero flow

The intersection of two perfect matchings ★★

Conjecture Every bridgeless cubic graph has two perfect matchings $M_1$ , $M_2$ so that $M_1 \cap M_2$ does not contain an odd edge-cut.

Keywords: cubic; nowhere-zero flow; perfect matching

Posted by mdevos
updated August 30th, 2007

add new comment

Graph Theory » Algebraic G.T.

Half-integral flow polynomial values ★★

Author(s): Mohar

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 nowhere-zero $k$ -flows in $G$ .

Conjecture $\Phi(G,5.5) > 0$ for every 2-edge-connected graph $G$ .

Keywords: nowhere-zero flow

Posted by mohar
updated May 31st, 2007

add new comment

Combinatorics » Matrices

A nowhere-zero point in a linear mapping ★★★

Author(s): Jaeger

Conjecture If ${\mathbb F}$ is a finite field with at least 4 elements and $A$ is an invertible $n \times n$ matrix with entries in ${\mathbb F}$ , then there are column vectors $x,y \in {\mathbb F}^n$ which have no coordinates equal to zero such that $Ax=y$ .

Keywords: invertible; nowhere-zero flow

Posted by mdevos
updated March 8th, 2007

add new comment

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

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

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

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

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

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