# Antisymmetric flows and strong colourings of oriented graphs

Annales de l'institut Fourier (1999)

- Volume: 49, Issue: 3, page 1037-1056
- ISSN: 0373-0956

## Access Full Article

top## Abstract

top## How to cite

topNešetřill, J., and Raspaud, André. "Antisymmetric flows and strong colourings of oriented graphs." Annales de l'institut Fourier 49.3 (1999): 1037-1056. <http://eudml.org/doc/75355>.

@article{Nešetřill1999,

abstract = {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 $\vec\{\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 $(\{\Bbb 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.},

author = {Nešetřill, J., Raspaud, André},

journal = {Annales de l'institut Fourier},

keywords = {flows; colorings; digraphs; abelian group},

language = {eng},

number = {3},

pages = {1037-1056},

publisher = {Association des Annales de l'Institut Fourier},

title = {Antisymmetric flows and strong colourings of oriented graphs},

url = {http://eudml.org/doc/75355},

volume = {49},

year = {1999},

}

TY - JOUR

AU - Nešetřill, J.

AU - Raspaud, André

TI - Antisymmetric flows and strong colourings of oriented graphs

JO - Annales de l'institut Fourier

PY - 1999

PB - Association des Annales de l'Institut Fourier

VL - 49

IS - 3

SP - 1037

EP - 1056

AB - 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 $\vec{\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 $({\Bbb 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.

LA - eng

KW - flows; colorings; digraphs; abelian group

UR - http://eudml.org/doc/75355

ER -

## References

top- [1] N. ALON, T.H. MARSHALL, Homorphisms of edge-coloured graphs and Coxeter groups, J. Alg. Comb., 8 (1998), 5-13. Zbl0911.05034MR99i:05074
- [2] K. APPEL, W. HAKEN, Every planar map is four colorable, Bull. Amer. Math. Soc., 82 (1976), 711-712. Zbl0331.05106MR54 #12561
- [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). Zbl0412.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. Zbl0910.05064
- [5] O.V. BORODIN, On acyclic colorings of planar graphs, Discrete Math., 25 (1979), 211-236. Zbl0406.05031MR81b:05043
- [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). Zbl0932.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. Zbl0956.05041MR99e:05046
- [8] A. BOUCHET, Nowhere-zero integral flows on a bidirected graph, J. Comb. Theory (B), 34 (1983), 279-292. Zbl0518.05058MR85d:05109
- [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. Zbl0265.05103MR47 #6531
- [12] H. FLEISCHNER, Eulerian graphs and related topics, Part 1, Vol. 2, Annals of Discrete Mathematics, 50, North-Holland Publishing Co., Amsterdam, 1991. Zbl0792.05092MR92f:05066
- [13] F. JAEGER, A Survey of cycle double cover conjecture, Cycles in Graphs, Ann. Discrete Math., 27 North-Holland, Amsterdam, 1985, 123-126. Zbl0585.05012MR87b:05082
- [14] F. JAEGER, Nowhere zero-flow Problems, Selected topics in Graph Theory 3, Academic Press, London 1988, 71-95. Zbl0658.05034MR1205397
- [15] F. JAEGER, Flows and generalized coloring theorems in graphs, J. Comb. Theory (B), 26 (1979), 205-216. Zbl0422.05028MR81j:05059
- [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. Zbl0617.90026MR88h:05045
- [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. Zbl0795.05058MR95i:05058
- [19] A.V. KOSTOCHKA, E. SOPENA, X. ZHU, Acyclic and oriented chromatic numbers of graphs, J. Graph Theory, 14, 4 (1997), 331-340. Zbl0873.05044MR98e:05051
- [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. Zbl0873.05042MR97k:05083
- [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. Zbl0806.05031MR95i:05060
- [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. Zbl0865.05039MR97f:05070
- [25] P.D. SEYMOUR, Nowhere-zero 6-flows, J. Comb. Theory (B), 30 (1981), 130-135. Zbl0474.05028MR82j:05079
- [26] P.D. SEYMOUR, Handbook of Combinatorics, edited by R. Graham, M. Grötschel and L. Lovász, 1995, 289-299. Zbl0845.05035
- [27] E. SOPENA, The chromatic number of oriented graphs, J. Graph Theory, 25 (1997), 191-205. Zbl0874.05026MR98c:05069
- [28] W.T. TUTTE, A contribution to the theory of chromatic polynomials, Canad. J. Math., 6 (1954), 80-91. Zbl0055.17101MR15,814c
- [29] W.T. TUTTE, A class of abelian groups, Canad. J. Math., 8 (1956), 13-28. Zbl0070.02302MR17,708a
- [30] C.Q. ZHANG, Integer flows and cycle covers of graphs, Pure and Applied Mathematics, Dekker, 1997. Zbl0866.05001
- [31] X. ZHU, On game chromatic number, to appear.
- [32] O. ZÝKA, Bidirected nowhere-zero flows, Thesis, Charles University, Praha, 1988.

## Citations in EuDML Documents

top## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.