Nowhere-zero flow
≈ 4 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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.
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. 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 |\delta^+(v)| \equiv |\delta^-(v)| \bmod k. N_M(G) = N_M(G/ e) - N_M(G\setminus e). Combining this with induction we can show N_M(G) is a polynomial in |M|-1 where |M| is the order of the group M. We call N_M(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. In particular N_{M_1}(G) = N_{M_2}(G) if |M_1| = |M_2|. The above results were proved by Tutte in 1953 when he was studying the Tutte polynomial, a generalization of the flow polynomial.
Bridgeless Planar Graphs
There is a duality between k-face colorings and k-flows for bridgeless planar graphs. To see this, let G be a directed bridgeless planar graph with a proper k-face-coloring with colors \{0, 1, \ldots, k-1\}. Construct a map \phi: E(G)\to \{-(k-1), \ldots, -1, 0, 1, \ldots, k-1\} by the following rule: if the edge e has a face of color x to the left and a face 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 an NZ k-flow. Using induction on |E(G)| Tutte proved the converse is also true. This can be expressed concisely as: \chi(G^*) = \phi(G), where the RHS is the flow number, the smallest k for which G permits a k-flow.
General Graphs
The duality is true for general M-flows as well: Let c be the face-coloring function with values in M. Define \phi_c(e) = c(r_1) - c(r_2) where r 1 is the face to the left of e and r 2 is to the right. For every M-circulation \phi there is a coloring function c such that \phi = \phi_c (proven by induction). c is a |E(G)|-face-coloring if and only if \phi_c is an NZ M-flow (straightforward). The duality follows by combining the last two points. We can specialize to M = \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 for arbitrary graphs (not just planar), we can use this to extend face-colorings to non-planar graphs. Let K = \Z_2 \times \Z_2 be the Klein-4 group. Then a cubic graph has a K-flow if and only if it is 3-edge-colorable. As a corollary a cubic graph that is 3-edge colorable is 4-face colorable. A graph is 4-face colorable if and only if it permits an NZ 4-flow (see Four color theorem). The Petersen graph does not have an NZ 4-flow, and this led to the 4-flow conjecture (see below). If G is a triangulation then G is 3-(vertex) colorable if and only if every vertex has even degree. By the first bullet, the dual graph G* is 2-colorable and thus bipartite and planar cubic. So G* has an NZ 3-flow and is thus 3-face colorable, making G 3-vertex colorable. Just as no graph with a loop edge has a proper vertex coloring, no graph with a bridge can have an NZ M-flow for any group M. Conversely, every bridgeless graph has an NZ \Z -flow (a form of Robbins' theorem).
References
Further reading
Text derived from https://en.wikipedia.org/w/index.php?oldid=1373778551 under CC BY-SA 4.0; modifications have been made.