Antisymmetric flows and strong colourings of oriented graphs (Q1296157)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Antisymmetric flows and strong colourings of oriented graphs |
scientific article |
Statements
Antisymmetric flows and strong colourings of oriented graphs (English)
0 references
12 July 1999
0 references
Let \(M\) be an abelian group with additive notation, and \(B\subset M\), \(0\notin B\), \(B\cap -B=\varnothing \). For an oriented graph \(G=(V,E),\) the authors define an \(M\)-antisymmetric flow to be a mapping \(\phi \) from \(E\) to \(B\) so that, for any \(S\subset V\), \[ \sum_{e\in S^{+}}\phi (e)-\sum_{e\in S^{-}}\phi (e)=0, \] where \(S^{+}\) is the set of edges which begin in \(S\) and terminate not in \(S, \) and \(S^{-}=(V\backslash S)^{+}.\) It is shown that an antisymmetric flow exists for any oriented graph without oriented 2-cut and that any planar graph has an orientation with a \((Z_6)^5\)-antisymmetric flow.
0 references
flows
0 references
colorings
0 references
digraphs
0 references
abelian group
0 references