Home » Subject » Graph Theory » Coloring » Nowhere-zero flows

The three 4-flows conjecture

Importance: Medium ✭✭
Author(s): DeVos, Matt
Subject: Graph Theory
» Coloring
» » Nowhere-zero flows
Keywords: nowhere-zero flow
Recomm. for undergrads: no
Prize: bottle of wine (DeVos)
Posted by: mdevos
on: March 7th, 2007
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 $.

A graph $ G $ has a nowhere-zero 4-flow if and only if there exist 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\A_i $ has a nowhere-zero 2-flow for $ 1 \le i \le 3 $. Thus, the above conjecture is true with room to spare for such graphs. Since every 4-edge-connected graph and every 3-edge-colorable cubic graph has a nowhere-zero 4-flow, this conjecture is automatically true for these families. As with the 5-flow conjecture or the cycle double cover conjecture, establishing this conjecture comes down to proving it for cubic graphs which are not 3-edge-colorable.

This conjecture is a consequence of the Petersen coloring conjecture, and it implies the Orientable cycle four cover conjecture. The latter implication follows immediately from the fact that every graph with a nowhere-zero 4-flow has an orientable cycle double cover. Actually, it is possible that for every graph $ G $ with no cut-edge, there exist disjoint sets $ A_B_1,B_2 \subseteq E(G) $ with $ A \cup B_1 \cup B_2 = E(G) $ and so that $ G\B_1 $ and $ G\B_2 $ have nowhere-zero 3-flows and $ G\A $ has a nowhere-zero 2-flow. The Petersen graph has such a decomposition ($ B_1 $ and $ B_2 $ should be alternate edges of some 8-circuit) and so does every graph with a nowhere-zero 4-flow. If this stronger statement is true, then it would imply the oriented eight cycle four cover conjecture.

Bibliography

[J] F. Jaeger, On circular flows in graphs. Finite and infinite sets, Vol. I, II (Eger, 1981), 391--402, Colloq. Math. Soc. János Bolyai, 37, North-Holland, Amsterdam, 1984.. MathSciNet


* indicates original appearance(s) of problem.
add new comment