Recent Activity

The additive basis conjecture ★★★

Author(s): Jaeger; Linial; Payan; Tarsi

\begin{conjecture} For every prime $p$, there is a constant $c(p)$ (possibly $c(p)=p$) so that the union (as multisets) of any $c(p)$ bases of the vector space $({\mathbb Z}_p)^n$ contains an additive basis. \end{conjecture}

Keywords: additive basis; matrix

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

Partitioning edge-connectivity ★★

Author(s): DeVos

\begin{question} Let $G$ be an $(a+b+2)$-\Def[edge-connected]{connectivity (graph theory)} graph. Does there exist a partition $\{A,B\}$ of $E(G)$ so that $(V,A)$ is $a$-edge-connected and $(V,B)$ is $b$-edge-connected? \end{question}

Keywords: edge-coloring; edge-connectivity

Acyclic edge-colouring ★★

Author(s): Fiamcik

\begin{conjecture} Every simple graph with maximum degree $\Delta$ has a proper $(\Delta+2)$-\Def[edge-colouring]{edge-coloring} so that every cycle contains edges of at least three distinct colours. \end{conjecture}

Keywords: edge-coloring

Packing T-joins ★★

Author(s): DeVos

\begin{conjecture} There exists a fixed constant $c$ (probably $c=1$ suffices) so that every graft with minimum $T$-cut size at least $k$ contains a $T$-join packing of size at least $(2/3)k-c$. \end{conjecture}

Keywords: packing; T-join

Decomposing eulerian graphs ★★★


\begin{conjecture} If $G$ is a 6-\Def[edge-connected]{connectivity (graph theory)} \Def[Eulerian graph]{eulerian graph} and $P$ is a 2-transition system for $G$, then $(G,P)$ has a compaible decomposition. \end{conjecture}

Keywords: cover; cycle; Eulerian

Faithful cycle covers ★★★

Author(s): Seymour

\begin{conjecture} If $G = (V,E)$ is a graph, $p : E \rightarrow {\mathbb Z}$ is admissable, and $p(e)$ is even for every $e \in E(G)$, then $(G,p)$ has a faithful cover. \end{conjecture}

Keywords: cover; cycle

(m,n)-cycle covers ★★★

Author(s): Celmins; Preissmann

\begin{conjecture} Every \Def[bridgeless]{bridge (graph theory)} graph has a (5,2)-cycle-cover. \end{conjecture}

Keywords: cover; cycle

The circular embedding conjecture ★★★

Author(s): Haggard

\begin{conjecture} Every 2-\Def[connected]{connectivity (graph theory)} graph may be \Def[embedded]{graph embedding} in a surface so that the boundary of each face is a cycle. \end{conjecture}

Keywords: cover; cycle

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


\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

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

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