Antisymmetric flows and strong colourings of oriented graphs
J. Nešetřill, André Raspaud · Annales de l’institut Fourier · 1999
The homomorphisms of oriented or undirected graphs, the oriented chromatic number, the relationship between acyclic colouring number and oriented chromatic number, have been recently intensely studied. For the purpose of duality, we define the notions of strong-oriented colouring and antisymmetric-flow. An antisymmetric-flow is a flow with values in an additive abelian group which uses no opposite elements of the group. We prove that the strong-oriented chromatic number χ → s (as the modular version of oriented chromatic number) is bounded for planar graphs. By duality we obtain that any oriented planar graph has a ( ℤ 6 ) 5 -antisymmetric-flow. Moreover we prove that any 3 -edge connected oriented graph G has an antisymmetric-flow with values in a group whose order depends only of the dimension of the cycle space of the graph G . We list several open problems analogous to those for nowhere-zero flows.