View source for Nowhere-zero flow

{{Short description|Concept in graph theory}}
In [[graph theory]], a '''nowhere-zero flow''' or '''NZ flow''' is a [[Flow network|network flow]] that is nowhere zero. It is intimately connected (by duality) to [[graph coloring|coloring]] [[planar graphs]].
== Definitions ==
Let ''G'' = (''V'',''E'') be a [[directed graph|digraph]] and let ''M'' be an [[abelian group]]. A map ''φ'': ''E'' → ''M'' is an '''''M''-circulation''' if for every [[vertex (graph theory)|vertex]] ''v'' ∈ ''V''
:<math>\sum_{e \in \delta^+(v)} \varphi(e) = \sum_{e \in \delta^-(v)} \varphi(e),</math>
where ''δ''<sup>+</sup>(''v'') denotes the set of edges out of ''v'' and ''δ''<sup>−</sup>(''v'') denotes the set of edges into ''v''. Sometimes, this condition is referred to as [[Kirchhoff's circuit laws|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 {{nowrap begin}}0 < |''φ''(''e'')| < ''k''{{nowrap end}} then ''φ'' is a '''''k''-flow.'''<ref name=":0">{{Cite book|title=Graph theory|last=Diestel|first= Reinhard|date = 30 June 2017|publisher=Springer |isbn=9783662536216|oclc=1048203362}}</ref>
=== Other notions ===
Let ''G'' = (''V'',''E'') be an [[undirected graph]]. An orientation of ''E'' is a '''modular''' ''k''-'''flow''' if for every vertex&nbsp;''v''&nbsp;∈&nbsp;''V'' we have:
:<math>|\delta^+(v)| \equiv |\delta^-(v)| \bmod k.</math><!-- why is this useful? -->
== 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 <math>\Z_k</math> flow exists if and only if a ''k''-flow exists.<ref name=":0" /> As a consequence if ''G'' admits a ''k''-flow then it admits an ''h''-flow where <math>h \geq k</math>.
* 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 ==
{{Main|Tutte polynomial|Deletion–contraction formula}}
Let <math>N_M(G)</math> be the number of ''M''-flows on ''G''. It satisfies the [[deletion–contraction formula]]:<ref name=":0" />
:<math>N_M(G) = N_M(G/ e) - N_M(G\setminus e).</math>
Combining this with induction we can show <math>N_M(G)</math> is a polynomial in <math>|M|-1</math> where <math>|M|</math> is the [[Order (group theory)|order]] of the group ''M''. We call <math>N_M(G)</math> 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 <math>N_{M_1}(G) = N_{M_2}(G)</math> if <math>|M_1| = |M_2|.</math>
The above results were proved by [[Tutte]] in 1953 when he was studying the [[Tutte polynomial]], a generalization of the flow polynomial.<ref>{{cite journal
| last = Tutte | first = W. T. | author-link = W. T. Tutte
| doi = 10.4153/CJM-1954-010-9
| journal = Canadian Journal of Mathematics
| pages = 80–91
| title = A contribution to the theory of chromatic polynomials
| volume = 6
| year = 1954}}</ref>
== Flow-coloring duality ==
{{Main|Graph coloring}}
===Bridgeless Planar Graphs===
There is a duality between ''k''-face [[Graph coloring|colorings]] and ''k''-flows for [[Bridge (graph theory)|bridgeless]] [[planar graph]]s. To see this, let ''G'' be a directed bridgeless planar graph with a proper ''k''-face-coloring with colors <math>\{0, 1, \ldots, k-1\}.</math> Construct a map
:<math>\phi: E(G)\to \{-(k-1), \ldots, -1, 0, 1, \ldots, k-1\}</math>
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 graph|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:<ref name=":0" />
:<math>\chi(G^*) = \phi(G),</math>
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 <math>c</math> be the face-coloring function with values in ''M''.
* Define <math>\phi_c(e) = c(r_1) - c(r_2)</math> where ''r''<sub>1</sub> is the face to the left of ''e'' and ''r''<sub>2</sub> is to the right.
* For every ''M''-circulation <math>\phi</math> there is a coloring function ''c'' such that <math>\phi = \phi_c</math> (proven by induction).
* ''c'' is a |''E''(''G'')|-face-coloring if and only if <math>\phi_c</math> is a NZ ''M''-flow (straightforward).
The duality follows by combining the last two points. We can specialize to <math>M = \Z_k</math> 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.<ref name=":0" />
== Applications ==
* ''G'' is 2-face-colorable if and only if every vertex has even degree (consider NZ 2-flows).<ref name=":0" />
* Let <math>K = \Z_2 \times \Z_2</math> be the [[Klein-4 group]]. Then a [[cubic graph]] has a ''K''-flow if and only if it is 3-[[Edge coloring|edge-colorable]]. As a corollary a cubic graph that is 3-edge colorable is 4-face colorable.<ref name=":0" />
*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 graph|bipartite]] and planar cubic. So ''G''* has a NZ 3-flow and is thus 3-face colorable, making ''G'' 3-vertex colorable.<ref name=":0" />
* Just as no graph with a [[glossary of graph theory|loop]] edge has a proper vertex coloring, no graph with a [[glossary of graph theory|bridge]] can have a NZ ''M''-flow for any group ''M''. Conversely, every [[bridgeless graph]] has a NZ <math>\Z</math>-flow (a form of [[Robbins' theorem]]).<ref>For a stronger result on the enumeration of <math>\Z</math>-flows with a bound on the maximum flow amount per edge, again using Robbins' theorem on totally cyclic orientations, see Theorem 2 of {{citation| last=Kochol |first=Martin |doi=10.1006/jctb.2001.2081 |issue=2|journal=Journal of Combinatorial Theory| mr=1889258|pages=260–269|series=Series B| title= Polynomials associated with nowhere-zero flows|volume=84|year=2002|doi-access=free}}</ref>
== Existence of ''k''-flows ==
{{unsolved|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?}}
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-[[glossary of graph theory|edge-connected]] graph has a 4-flow.<ref>F. Jaeger, Flows and generalized coloring theorems in graphs, J. Comb. Theory Set. B, 26 (1979), 205–216.</ref>
:'''[[Paul_Seymour_(mathematician)|Seymour]]'s 6-flow Theorem.''' Every bridgeless graph has a 6-flow.<ref>P. D. Seymour, Nowhere-zero 6-flows, J. Comb. Theory Ser B, 30 (1981), 130–135.</ref>
=== 3-flow, 4-flow and 5-flow conjectures ===
As of 2019, the following are currently unsolved (due to [[W. T. Tutte|Tutte]]):
:'''3-flow Conjecture.''' Every 4-edge-connected graph has a nowhere-zero 3-flow.<ref>[http://www.openproblemgarden.org/op/3_flow_conjecture], Open Problem Garden.</ref>
:'''4-flow Conjecture.''' Every bridgeless graph that does not have the [[Petersen graph]] as a [[minor (graph theory)|minor]] has a nowhere-zero 4-flow.<ref>[http://www.openproblemgarden.org/op/4_flow_conjecture], Open Problem Garden.</ref>
:'''5-flow Conjecture.''' Every bridgeless graph has a nowhere-zero 5-flow.<ref>[http://www.openproblemgarden.org/op/5_flow_conjecture], Open Problem Garden.</ref>
The converse of the 4-flow Conjecture does not hold since the [[complete graph]] ''K''<sub>11</sub> contains a Petersen graph ''and'' a 4-flow.<ref name=":0" /> For bridgeless [[cubic graph]]s with no Petersen minor, 4-flows exist by the [[Snark (graph theory)|snark theorem]] (Seymour, et al 1998, not yet published). The [[four color theorem]] is equivalent to the statement that no snark is planar.<ref name=":0" />
== See also ==
*[[Cycle space]]
*[[Cycle double cover|Cycle double cover conjecture]]
*[[Four color theorem]]
*[[Graph coloring]]
*[[Edge coloring]]
*[[Tutte polynomial]]
==References==
{{reflist}}
==Further reading==
*{{cite book|last = Zhang |first = Cun-Quan |title = Integer Flows and Cycle Covers of Graphs |url= https://archive.org/details/integerflowscycl0000zhan |series = Chapman & Hall/CRC Pure and Applied Mathematics Series |year = 1997 |publisher = Marcel Dekker, Inc. |isbn = 9780824797904 |lccn = 96037152
|url-access = registration}}
*{{cite book|last = Zhang | first = Cun-Quan | isbn = 978-0-5212-8235-2| publisher = Cambridge University Press | title = Circuit Double Cover of Graphs
| year = 2012}}
*{{cite book|last1 = Jensen | first1 = T. R. | last2 = Toft | first2 = B. | series = Wiley-Interscience Serires in Discrete Mathematics and Optimization
| chapter = 13 Orientations and Flows | pages = [https://archive.org/details/graphcoloringpro00jens_979/page/n230 209]–219 | title = Graph Coloring Problems | url = https://archive.org/details/graphcoloringpro00jens_979 | url-access = limited | year = 1995| isbn = 9780471028659 }}
*{{cite journal|last1 = Jacobsen | first1 = Jesper Lykke | last2 = Salas | first2 = Jesús | arxiv = 1009.4062 | doi = 10.1016/j.jctb.2013.06.001| issue = 4 | journal = Journal of Combinatorial Theory | mr = 3071381 | pages = 532–565 | series = Series B | title = Is the five-flow conjecture almost false?| volume = 103 | year = 2013| s2cid = 41483928 }}
[[Category:Network flow problem]]