Nowhere-zero flow

In graph theory, a nowhere-zero flow or NZ flow is a network flow that is nowhere zero. It is intimately connected (by duality) to coloring planar graphs.

Definitions

Let G = (V,E) be a digraph and let M be an abelian group. A map φ: E → M is an M-circulation if for every vertex v ∈ V

\sum _{e\in \delta ^{+}(v)}\varphi (e)=\sum _{e\in \delta ^{-}(v)}\varphi (e),

where δ⁺(v) denotes the set of edges out of v and δ⁻(v) denotes the set of edges into v. Sometimes, this condition is referred to as Kirchhoff's law.

If φ(e) ≠ 0 for every e ∈ E, we call φ a nowhere-zero flow, an M-flow, or an NZ-flow. If k is an integer and 0 < |φ(e)| < k then φ is a k-flow.^[1]

Other notions

Let G = (V,E) be an undirected graph. An orientation of E is a modular k-flow if

|\delta ^{+}(v)|\equiv |\delta ^{-}(v)|{\pmod {k}}

for every vertex v ∈ V.

Properties

Orientation independence. Modify a nowhere-zero flow φ on a graph G by choosing an edge e, reversing it, and then replacing φ(e) with -φ(e). After this adjustment, φ is still a nowhere-zero flow. Furthermore, if φ was originally a k-flow, then the resulting φ is also a k-flow. Thus, the existence of a nowhere-zero M-flow or a nowhere-zero k-flow is independent of the orientation of the graph. Thus, an undirected graph G is said to have a nowhere-zero M-flow or nowhere-zero k-flow if some (and thus every) orientation of G has such a flow.
If G admits a k-flow then it admits an h-flow where $h\geq k$ .
The set of M-flows do not necessarily form a group as the sum of two flows on one edge may add to 0.
(Tutte 1950) A graph G has an M-flow iff it has a |M|-flow. As a consequence, a $\mathbb {Z} _{k}$ flow exists iff a k-flow exists.^[1]

Flow polynomial

Let N(G) be the number of M-flows on G. It satisfies the deletion–contraction formula N(G) = N(G / e) - N(G \ e).

Using this and induction, it can be shown that N(G) is a polynomial in $|M|-1$ where |M| is the order of the group M. We call N(G) the flow polynomial of G and abelian group M.

The above implies that two groups of equal order have an equal number of NZ flows. The order is the only group parameter that matters, not the structure of M.

The above results were proved by Tutte in 1953 when he was studying the Tutte polynomial, a generalization of the flow polynomial.^[2]

Flow-coloring duality

There is a duality between region region-colorings and M-flows.

Let G be a directed bridgeless planar graph, and assume that the regions of this drawing are properly k-colored with the colors {0, 1, 2, .., k – 1}.

Construct a map φ: E(G) → {–(k – 1), ..., –1, 0, 1, ..., 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. Then φ is a (NZ) k-flow since x and y must be different colors.

So if G and G* are planar dual graphs and G* is k-colorable (there is a coloring of the faces of G), then G has a NZ k-flow. Tutte proved that the converse is also true (use induction on |E(G)| ).^[1]

In general:

Let $c(r)\in M$ for each region r be the coloring function
Define $\phi _{c}(e)=c(r_{1})-c(r_{2})$ where r1 is the region to the left of e and r2 is to the right
For every M-circulation $\phi$ there is a coloring function c such that $\phi =\phi _{c}$ (prove by induction)
c is a |E(G)|-region-coloring iff $\phi _{c}$ is a NZ M-flow (straightforward)

The duality follows by combining the last two points. We can specialize to $M=\mathbb {Z} _{k}$ to obtain the similar results for k-flows discussed above. Given this duality between NZ flows and colorings, and since we can define NZ flows to arbitrary graphs (not just planar), we can use this to extend coloring theory to non-planar graphs.

Theory

Unsolved problem in mathematics

Does every bridgeless graph have a nowhere zero 5-flow? Does every bridgeless graph that does not have the Petersen graph as a minor have a nowhere zero 4-flow?

References

^ ^a ^b ^c Diestel, Reinhard, 1959- Verfasser. Graph theory. ISBN 9783662536216. OCLC 1048203362. {{cite book}}: |last= has generic name (help)CS1 maint: multiple names: authors list (link) CS1 maint: numeric names: authors list (link)
^ Tutte, William Thomas (1953). "A contribution to the theory of chromatic polynomials". {{cite journal}}: Cite journal requires |journal= (help)
^ F. Jaeger, Flows and generalized coloring theorems in graphs, J. Comb. Theory Set. B, 26 (1979), 205-216.
^ P. D. Seymour, Nowhere-zero 6-flows, J. Comb. Theory Ser B, 30 (1981), 130-135.
^ 5-flow conjecture, Open Problem Garden.
^ 4-flow conjecture, Open Problem Garden.