Nowhere-zero flow
In graph theory, nowhere-zero flows are a special type of network flow which is related (by duality) to coloring planar graphs.
Definition
Let G = (V,E) be a directed graph and let M be an abelian group. A map φ: E → M is a flow or an M-flow if for every vertex v ∈ V, it holds that
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. If M = Z is the group of integers under addition and k is a positive integer with the property that –k < φ(e) < k for every edge e, then the M-flow φ is also called a k-flow.
Let G = (V,E) be an undirected graph. An orientation of E is a modular k-flow if
for every vertex v ∈ V.
Properties
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.
More surprisingly, if M is a finite abelian group of size k, then the number of a nowhere-zero M-flows in some graph does not depend on the structure of M but only on k, the size of M. Furthermore, the existence of a M-flow coincides with the existence of a k-flow. These two results were proved by Tutte in 1953.[1]
Flow/coloring duality
Let G = (V,E) be a directed bridgeless 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 φ: 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. 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.
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? (more unsolved problems in mathematics) |
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 Z-flow (a form of Robbins theorem), but interesting questions arise when trying 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)[2] and Seymour's 6-flow theorem (every bridgeless graph has a nowhere-zero 6-flow).[3]
Tutte conjectured that every bridgeless graph has a nowhere-zero 5-flow[4] and that every bridgeless graph that does not have the Petersen graph as a minor has a nowhere-zero 4-flow.[5] For cubic graphs with no Petersen minor, a 4-flow is known to exist as a consequence of the snark theorem but for arbitrary graphs these conjectures remain open.
See also
References
- ↑ Tutte, William Thomas (1953). "A contribution to the theory of chromatic polynomials".
- ↑ 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.
Additional 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.