Open Problem Garden

Graph Theory » Basic G.T. » Cycles

(m,n)-cycle covers ★★★

Author(s): Celmins; Preissmann

Conjecture Every bridgeless graph has a (5,2)-cycle-cover.

Keywords: cover; cycle

Posted by mdevos
updated March 7th, 2007

add new comment

Graph Theory » Basic G.T. » Cycles

The circular embedding conjecture ★★★

Author(s): Haggard

Conjecture Every 2-connected graph may be embedded in a surface so that the boundary of each face is a cycle.

Keywords: cover; cycle

Posted by mdevos
updated March 7th, 2007

add new comment

Graph Theory » Basic G.T. » Cycles

Cycle double cover conjecture ★★★★

Author(s): Seymour; Szekeres

Conjecture For every graph with no bridge, there is a list of cycles so that every edge is contained in exactly two.

Keywords: cover; cycle

Posted by mdevos
updated February 7th, 2012

3 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

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