Antisymmetric flows and strong colourings of oriented graphs

Nešetřill, J.; Raspaud, André

Annales de l'Institut Fourier, Tome 49 (1999) no. 3, pp. 1037-1056.

Les homomorphismes de graphes orientés ou non orientés, le nombre chromatique orienté, la relation entre le nombre chromatique acyclique et le nombre chromatique orienté, ont été très étudiés ces dernières années. Dans le but de définir des notions duales, nous introduisons les notions de coloration orientée forte et de flot antisymétrique. Un flot antisymétrique est un flot à valeurs dans un groupe abélien qui n’utilise pas d’éléments opposés du groupe. Nous montrons que le nombre chromatique orienté fort ${\overrightarrow{\chi }}_s$ (version modulaire du nombre chromatique orienté) est borné pour les graphes planaires; par dualité nous obtenons que tout graphe planaire admet un flot antisymétrique à valeurs dans $({\mathbb{Z}}_6{)}^5$. Nous prouvons de plus que tout graphe orienté $3$-arête connexe a un flot antisymétrique à valeurs dans un groupe dont l’ordre ne dépend que de la dimension de l’espace des cycles du graphe. Nous terminons par plusieurs problèmes ouverts analogues aux problèmes des flots non-nul.

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 ${\overrightarrow{\chi }}_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 $({\mathbb{Z}}_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.

[1] N. Alon, T.H. Marshall, Homorphisms of edge-coloured graphs and Coxeter groups, J. Alg. Comb., 8 (1998), 5-13. | MR | Zbl

[2] K. Appel, W. Haken, Every planar map is four colorable, Bull. Amer. Math. Soc., 82 (1976), 711-712. | MR | Zbl

[3] L. Babai, Embedding graphs in Cayley graphs, Problèmes combinatoires et théorie des graphes, Orsay 1976, Colloq. int. CNRS n°260, 13-15 (1978). | Zbl

[4] W. Bienia, L. Goddyn, P. Gvozdjak, A. Sebö, M. Tarsi, Flows, view-obstructions, and the lonely runner, J. Comb. Theory (B), 72 (1998), 1-9. | Zbl

[5] O.V. Borodin, On acyclic colorings of planar graphs, Discrete Math., 25 (1979), 211-236. | MR | Zbl

[6] O.V. Borodin, A.V. Kostochka, J. Nešetřil, A. Raspaud, E. Sopena, On the maximum average degree and the oriented chromatic number of a graph, Discrete Math. (to appear). | Zbl

[7] O.V. Borodin, A.V. Kostochka, J. Nešetřil, A. Raspaud, E. Sopena, On universal graphs for planar oriented graphs of a given girth, Discrete Math., 188 1-3 (1998), 73-85. | MR | Zbl

[8] A. Bouchet, Nowhere-zero integral flows on a bidirected graph, J. Comb. Theory (B), 34 (1983), 279-292. | MR | Zbl

[9] U.A. Celmins, On cubic graphs that do not have an edge 3-coloring, Ph. D. Thesis, University of Waterloo, Waterloo, Canada, 1984.

[10] H. Grötsch, Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel, Wiss. Z. Martin Luther Univ. Halle Wittenberg, Math.-Nat. Reihe, 8 (1959), 109-120.

[11] B. Grünbaum, Acyclic Coloring of Planar Graphs, Israel J. Math., 14 (1973), 390-412. | MR | Zbl

[12] H. Fleischner, Eulerian graphs and related topics, Part 1, Vol. 2, Annals of Discrete Mathematics, 50, North-Holland Publishing Co., Amsterdam, 1991. | MR | Zbl

[13] F. Jaeger, A Survey of cycle double cover conjecture, Cycles in Graphs, Ann. Discrete Math., 27 North-Holland, Amsterdam, 1985, 123-126. | MR | Zbl

[14] F. Jaeger, Nowhere zero-flow Problems, Selected topics in Graph Theory 3, Academic Press, London 1988, 71-95. | MR | Zbl

[15] F. Jaeger, Flows and generalized coloring theorems in graphs, J. Comb. Theory (B), 26 (1979), 205-216. | MR | Zbl

[16] A.B. Kempe, On the geographical problem of four colours, Amer. J. Math., 2 (1879), 193-200.

[17] A. Khelladi, Nowhere-zero integral chains and flows in bidirected graphs, J. Comb. Theory (B), 43 (1987), 95-115. | MR | Zbl

[18] H.A. Kierstead, S.G. Penrice, W.T. Trotter, On-line coloring and recursive graph theory, SIAM J. Discrete Math., 7, n° 1 (1994), 72-89. | MR | Zbl

[19] A.V. Kostochka, E. Sopena, X. Zhu, Acyclic and oriented chromatic numbers of graphs, J. Graph Theory, 14, 4 (1997), 331-340. | MR | Zbl

[20] J. Nešetřil, A. Raspaud, E. Sopena, Colorings and girth of oriented planar graphs, Discrete Math., 165-166 (1-3) (1997), 519-530. | MR | Zbl

[21] J. Nešetřil, A. Raspaud, Colored Homomorphisms of colored mixed graphs, KAM-DIMATIA Series 98-376 KAM Charles University Prague (Czech Republic), to appear in J. Comb. Theory (B).

[22] M. Preissmann, Sur les colorations des arêtes des graphes cubiques, Thèse de Doctorat de 3e cycle, Université de Grenoble, 1981.

[23] A. Raspaud, E. Sopena, Good and semi-strong colorings of oriented planar graphs, Inf. Processing Letters, 51 (1994), 171-174. | MR | Zbl

[24] N. Robertson, D.P. Sanders, P.D. Seymour, R. Thomas, A new proof of the four-colour theorem, Electron. Res. Announc., Am. Math. Soc., 02, n° 1 (1996), 17-25. | MR | Zbl

[25] P.D. Seymour, Nowhere-zero 6-flows, J. Comb. Theory (B), 30 (1981), 130-135. | MR | Zbl

[26] P.D. Seymour, Handbook of Combinatorics, edited by R. Graham, M. Grötschel and L. Lovász, 1995, 289-299. | Zbl

[27] E. Sopena, The chromatic number of oriented graphs, J. Graph Theory, 25 (1997), 191-205. | MR | Zbl

[28] W.T. Tutte, A contribution to the theory of chromatic polynomials, Canad. J. Math., 6 (1954), 80-91. | MR | Zbl

[29] W.T. Tutte, A class of abelian groups, Canad. J. Math., 8 (1956), 13-28. | MR | Zbl

[30] C.Q. Zhang, Integer flows and cycle covers of graphs, Pure and Applied Mathematics, Dekker, 1997. | Zbl

[31] X. Zhu, On game chromatic number, to appear.

[32] O. Zýka, Bidirected nowhere-zero flows, Thesis, Charles University, Praha, 1988.