nowhere-zero flow


The intersection of two perfect matchings ★★

Author(s): Macajova; Skoviera

\begin{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. \end{conjecture}

Keywords: cubic; nowhere-zero flow; perfect matching

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 \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}

Keywords: nowhere-zero flow

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

Author(s): Jaeger

\begin{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$. \end{conjecture}

Keywords: invertible; 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

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

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

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

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

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

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

Syndicate content