Misplaced Pages

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

${\displaystyle \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.

Other notions

Let G = (V,E) be an undirected graph. An orientation of E is a modular k-flow if for every vertex v ∈ V we have:

${\displaystyle |\delta ^{+}(v)|\equiv |\delta ^{-}(v)|{\bmod {k}}.}$

Properties

• The set of M-flows does 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 if and only if it has a |M|-flow. As a consequence, a ${\displaystyle \mathbb {Z} _{k}}$ flow exists if and only if a k-flow exists. As a consequence if G admits a k-flow then it admits an h-flow where ${\displaystyle h\geq k}$.

• 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.

Flow polynomial

Let ${\displaystyle N_{M}(G)}$ be the number of M-flows on G. It satisfies the deletion–contraction formula:

${\displaystyle N_{M}(G)=N_{M}(G/e)-N_{M}(G\setminus e).}$

Combining this with induction we can show ${\displaystyle N_{M}(G)}$ is a polynomial in ${\displaystyle |M|-1}$ where ${\displaystyle |M|}$ is the order of the group M. We call ${\displaystyle 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 ${\displaystyle N_{M_{1}}(G)=N_{M_{2}}(G)}$ if ${\displaystyle |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.

Flow-coloring duality

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 ${\displaystyle \{0,1,\ldots ,k-1\}.}$ Construct a map

${\displaystyle \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 a NZ k-flow. Using induction on |E(G)| Tutte proved the converse is also true. This can be expressed concisely as:

${\displaystyle \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 ${\displaystyle c}$ be the face-coloring function with values in M.

• Define ${\displaystyle \phi _{c}(e)=c(r_{1})-c(r_{2})}$ where r₁ is the face to the left of e and r₂ is to the right.

• For every M-circulation ${\displaystyle \phi }$ there is a coloring function c such that ${\displaystyle \phi =\phi _{c}}$ (proven by induction).

• c is a |E(G)|-face-coloring if and only if ${\displaystyle \phi _{c}}$ is a NZ M-flow (straightforward).

The duality follows by combining the last two points. We can specialize to ${\displaystyle 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 for arbitrary graphs (not just planar), we can use this to extend face-colorings to non-planar graphs.

Applications

• G is 2-face-colorable if and only if every vertex has even degree (consider NZ 2-flows).

• Let ${\displaystyle K=\mathbb {Z} _{2}\times \mathbb {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 a NZ 4-flow (see Four color theorem). The Petersen graph does not have a 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 a 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 a NZ M-flow for any group M. Conversely, every bridgeless graph has a NZ ${\displaystyle \mathbb {Z} }$-flow (a form of Robbins' theorem).

Existence of k-flows

Interesting questions arise when trying to find nowhere-zero k-flows for small values of k. The following have been proven:

Jaeger's 4-flow Theorem. Every 4-edge-connected graph has a 4-flow.

Seymour's 6-flow Theorem. Every bridgeless graph has a 6-flow.

3-flow, 4-flow and 5-flow conjectures

As of 2019, the following are currently unsolved (due to Tutte):

3-flow Conjecture. Every 4-edge-connected graph has a nowhere-zero 3-flow.

4-flow Conjecture. Every bridgeless graph that does not have the Petersen graph as a minor has a nowhere-zero 4-flow.

5-flow Conjecture. Every bridgeless graph has a nowhere-zero 5-flow.

The converse of the 4-flow Conjecture does not hold since the complete graph K₁₁ contains a Petersen graph and a 4-flow. For bridgeless cubic graphs with no Petersen minor, 4-flows exist by the snark theorem (Seymour, et al 1998, not yet published). The four color theorem is equivalent to the statement that no snark is planar.

See also

• Cycle space
• Cycle double cover conjecture
• Four color theorem
• Graph coloring
• Edge coloring
• Tutte polynomial

References

1. ^ Diestel, Reinhard (30 June 2017). Graph theory. Springer. ISBN 9783662536216. OCLC 1048203362.
2. Tutte, W. T. (1954). "A contribution to the theory of chromatic polynomials". Canadian Journal of Mathematics. 6: 80–91. doi:10.4153/CJM-1954-010-9.
3. For a stronger result on the enumeration of ${\displaystyle \mathbb {Z} }$-flows with a bound on the maximum flow amount per edge, again using Robbins' theorem on totally cyclic orientations, see Theorem 2 of Kochol, Martin (2002), "Polynomials associated with nowhere-zero flows", Journal of Combinatorial Theory, Series B, 84 (2): 260–269, doi:10.1006/jctb.2001.2081, MR 1889258
4. F. Jaeger, Flows and generalized coloring theorems in graphs, J. Comb. Theory Set. B, 26 (1979), 205–216.
5. P. D. Seymour, Nowhere-zero 6-flows, J. Comb. Theory Ser B, 30 (1981), 130–135.
6. , Open Problem Garden.
7. , Open Problem Garden.
8. , Open Problem Garden.

Further reading

• Zhang, Cun-Quan (1997). Integer Flows and Cycle Covers of Graphs. Chapman & Hall/CRC Pure and Applied Mathematics Series. Marcel Dekker, Inc. ISBN 9780824797904. LCCN 96037152.
• Zhang, Cun-Quan (2012). Circuit Double Cover of Graphs. Cambridge University Press. ISBN 978-0-5212-8235-2.
• Jensen, T. R.; Toft, B. (1995). "13 Orientations and Flows". Graph Coloring Problems. Wiley-Interscience Serires in Discrete Mathematics and Optimization. pp. 209–219. ISBN 9780471028659.
• Jacobsen, Jesper Lykke; Salas, Jesús (2013). "Is the five-flow conjecture almost false?". Journal of Combinatorial Theory. Series B. 103 (4): 532–565. arXiv:1009.4062. doi:10.1016/j.jctb.2013.06.001. MR 3071381. S2CID 41483928.

• Network flow problem