Nowhere-zero flows

From Wikipedia, the free encyclopedia

In graph theory, nowhere-zero flows are a special type of network flow which is related (by duality) to coloring planar graphs. Let G = (V,E) be a directed graph and let M be an abelian group. We say that a map \phi : E \rightarrow M is a flow or an M-flow if the following condition (sometimes called the Kirchoff Rule) is satisfied at every vertex v \in V (here we let δ + (v) denote the set of edges pointing away from v and δ − (v) the set of edges pointing toward v).

\sum_{e \in \delta^+(v)} \phi(e) = \sum_{e \in \delta^-(v)} \phi(e)

If \phi(e) \neq 0 for every e \in E, we call φ a nowhere-zero flow. If M = {\mathbb Z} and k is a positive integer with the property that Failed to parse (Cannot write to or create math output directory): -k < \phi(e) <k

for every edge e, we say that φ is a k-flow.

Consider a flow φ on G and modify it by choosing an edge e \in E, reversing it, and then replacing φ(e) with − φ(e). After this adjustment, φ is still a flow, and further this adjustment preserves the properties k-flow and nowhere-zero flow. Thus, the existence of a nowhere-zero M-flow and the existence of a nowhere-zero k-flow is independent of the orientation of the graph, and we will say that an (undirected) graph has a nowhere-zero M-flow or k-flow if some (and thus every) orientation of it has such a flow.

[edit] Flow/coloring duality

Let G = (V,E) be a directed graph drawn in the plane, and assume that the regions of this drawing are properly k-colored with the colors {0, 1, 2, .., k − 1}. Now, construct a map \phi:E(G)\rightarrow\{-(k-1),\dots,-1,0,1,\dots,k-1\} by the following rule: if the edge e has a region of color x to the left and a region of color y to the right, then let φ(e) = x − y. It is an easy exercise to show that φ is a k-flow. Furthermore, since the regions were properly colored, φ is a nowhere-zero k-flow. It follows from this construction, that if G and G * are planar dual graphs and G * is k-colorable, then G has a nowhere-zero k-flow. Tutte proved that the converse of this statement is also true. Thus, for planar graphs, nowhere-zero flows are dual to colorings. Since nowhere-zero flows make sense for general graphs (not just graphs drawn in the plane), this study can be viewed as an extension of coloring theory for non-planar graphs.

[edit] Theory

Just as no graph with a loop edge has a proper coloring, no graph with a bridge can have a nowhere-zero flow (in any group). It is easy to show that every graph without a bridge has a nowhere-zero {\mathbb Z}-flow, but interesting questions arise when we try to find nowhere-zero k-flows for small values of k. Two nice theorems in this direction are Jaeger's 4-flow theorem (every 4-edge-connected graph has a nowhere-zero 4-flow) and Seymour's 6-flow theorem (every bridgeless graph has a nowhere-zero 6-flow.