Importance: Medium ✭✭
 Author(s): DeVos, Matt
 Subject: Graph Theory » Coloring » » Nowhere-zero flows
 Keywords: homomorphism nowhere-zero flow tension
 Prize: bottle of wine (DeVos)
 Posted by: mdevos on: March 7th, 2007
Conjecture   Let be abelian groups and let and satisfy and . If there is a homomorphism from to , then every graph with a B-flow has a B'-flow.

Definition:Let be a directed graph, Let be an abelian group, and let be a subset of such that . We say that a flow or a tension is a -flow or a -tension if the range is a subset of . If is a -flow (-tension) of and we reverse the direction of the edge , then we may obtain a new -flow (-tension) by changing to . Thus, the existence of a -flow or -tension does not depend on the orientation, and we say that an undirected graph has a -flow or a -tension if some (and thus every) orientation of it admits such a map. We define the Cayley graph to be the simple graph with vertex set in which two vertices are joined by an edge if and only if .

It is well known that a graph has a -tension if and only if it has a homomorphism to . So, if are as in the conjecture and there is a homomorphism from to , then every graph G with a -tension has a -tension. This follows from the previous sentence and the fact that the composition of two homomorphisms is another homomorphism. In essence, the above conjecture states that the same equivalence should hold true for flows.

If and are directed planar dual graphs (each edge of crosses left to right over the corresponding edge of ), then a map is a tension if and only if the dual map ( is given by the rule ) is a flow of . Thus, planar duality exchanges flows and tensions. For two undirected planar dual graphs, and we have that G has a -flow if and only if has a -tension. It follows from this duality and the observation from the previous paragraph, that the above conjecture is true for planar graphs.

This conjecture is also known in the special case when and . In this case, and are the complete graphs on and vertices respectively, so there is a homomorphism from to if and only if is greater than or equal to . Thus, in this case the conjecture is equivalent to the assertion that every graph with a nowhere-zero -flow also has a nowhere-zero -flow if is at least . This statement is true by a result of Tutte.