Recent Activity

Packing T-joins ★★

Author(s): DeVos

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

Keywords: packing; T-join

Posted by mdevos
updated March 7th, 2007

add new comment

Graph Theory » Basic G.T. » Cycles

Decomposing eulerian graphs ★★★

Author(s):

Conjecture If $G$ is a 6-edge-connected Eulerian graph and $P$ is a 2-transition system for $G$ , then $(G,P)$ has a compaible decomposition.

Keywords: cover; cycle; Eulerian

Posted by mdevos
updated March 7th, 2007

add new comment

Graph Theory » Basic G.T. » Cycles

Faithful cycle covers ★★★

Author(s): Seymour

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.

Keywords: cover; cycle

Posted by mdevos
updated March 7th, 2007

add new comment

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 » 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

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