Antisymmetric flows and strong colourings of oriented graphs
Nešetřill, J. ; Raspaud, André
Annales de l'Institut Fourier, Tome 49 (1999), p. 1037-1056 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

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 χ → 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 (ℤ 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 χ → 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.

@article{AIF_1999__49_3_1037_0,
     author = {Ne\v set\v rill, J. and Raspaud, Andr\'e},
     title = {Antisymmetric flows and strong colourings of oriented graphs},
     journal = {Annales de l'Institut Fourier},
     volume = {49},
     year = {1999},
     pages = {1037-1056},
     doi = {10.5802/aif.1705},
     mrnumber = {2002a:05107},
     zbl = {0921.05034},
     language = {en},
     url = {http://dml.mathdoc.fr/item/AIF_1999__49_3_1037_0}
}

Nešetřill, J.; Raspaud, André. Antisymmetric flows and strong colourings of oriented graphs. Annales de l'Institut Fourier, Tome 49 (1999) pp. 1037-1056. doi : 10.5802/aif.1705. http://gdmltest.u-ga.fr/item/AIF_1999__49_3_1037_0/

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

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

[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 0412.05037

[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 0910.05064

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

[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 0932.05033

[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 99e:05046 | Zbl 0956.05041

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

[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 47 #6531 | Zbl 0265.05103

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

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

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

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

[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 88h:05045 | Zbl 0617.90026

[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 95i:05058 | Zbl 0795.05058

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

[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 97k:05083 | Zbl 0873.05042

[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 95i:05060 | Zbl 0806.05031

[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 97f:05070 | Zbl 0865.05039

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

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

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

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

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

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

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

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