Antisymmetric flows and strong colourings of oriented graphs

J. Nešetřill; André Raspaud

Annales de l'institut Fourier (1999)

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

Abstract

top
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.

How to cite

top

Neš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. [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. [2] K. APPEL, W. HAKEN, Every planar map is four colorable, Bull. Amer. Math. Soc., 82 (1976), 711-712. Zbl0331.05106MR54 #12561
  3. [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. [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. [5] O.V. BORODIN, On acyclic colorings of planar graphs, Discrete Math., 25 (1979), 211-236. Zbl0406.05031MR81b:05043
  6. [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. [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. [8] A. BOUCHET, Nowhere-zero integral flows on a bidirected graph, J. Comb. Theory (B), 34 (1983), 279-292. Zbl0518.05058MR85d:05109
  9. [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. [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. [11] B. GRÜNBAUM, Acyclic Coloring of Planar Graphs, Israel J. Math., 14 (1973), 390-412. Zbl0265.05103MR47 #6531
  12. [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. [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. [14] F. JAEGER, Nowhere zero-flow Problems, Selected topics in Graph Theory 3, Academic Press, London 1988, 71-95. Zbl0658.05034MR1205397
  15. [15] F. JAEGER, Flows and generalized coloring theorems in graphs, J. Comb. Theory (B), 26 (1979), 205-216. Zbl0422.05028MR81j:05059
  16. [16] A.B. KEMPE, On the geographical problem of four colours, Amer. J. Math., 2 (1879), 193-200. 
  17. [17] A. KHELLADI, Nowhere-zero integral chains and flows in bidirected graphs, J. Comb. Theory (B), 43 (1987), 95-115. Zbl0617.90026MR88h:05045
  18. [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. [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. [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. [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. [22] M. PREISSMANN, Sur les colorations des arêtes des graphes cubiques, Thèse de Doctorat de 3e cycle, Université de Grenoble, 1981. 
  23. [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. [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. [25] P.D. SEYMOUR, Nowhere-zero 6-flows, J. Comb. Theory (B), 30 (1981), 130-135. Zbl0474.05028MR82j:05079
  26. [26] P.D. SEYMOUR, Handbook of Combinatorics, edited by R. Graham, M. Grötschel and L. Lovász, 1995, 289-299. Zbl0845.05035
  27. [27] E. SOPENA, The chromatic number of oriented graphs, J. Graph Theory, 25 (1997), 191-205. Zbl0874.05026MR98c:05069
  28. [28] W.T. TUTTE, A contribution to the theory of chromatic polynomials, Canad. J. Math., 6 (1954), 80-91. Zbl0055.17101MR15,814c
  29. [29] W.T. TUTTE, A class of abelian groups, Canad. J. Math., 8 (1956), 13-28. Zbl0070.02302MR17,708a
  30. [30] C.Q. ZHANG, Integer flows and cycle covers of graphs, Pure and Applied Mathematics, Dekker, 1997. Zbl0866.05001
  31. [31] X. ZHU, On game chromatic number, to appear. 
  32. [32] O. ZÝKA, Bidirected nowhere-zero flows, Thesis, Charles University, Praha, 1988. 

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.