Geodesic
Oriented colouring of some graph products
Discussiones Mathematicae. Graph Theory, Tome 31 (2011) no. 4, pp. 675-686.

Voir la notice de l'article provenant de la source Library of Science

We obtain some improved upper and lower bounds on the oriented chromatic number for different classes of products of graphs.
Keywords: oriented colouring 
@article{DMGT_2011_31_4_a3,
     author = {Aravind, N. and Narayanan, N. and Subramanian, C.},
     title = {Oriented colouring of some graph products},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {675--686},
     publisher = {mathdoc},
     volume = {31},
     number = {4},
     year = {2011},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2011_31_4_a3/}
}
TY  - JOUR
AU  - Aravind, N.
AU  - Narayanan, N.
AU  - Subramanian, C.
TI  - Oriented colouring of some graph products
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2011
SP  - 675
EP  - 686
VL  - 31
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2011_31_4_a3/
LA  - en
ID  - DMGT_2011_31_4_a3
ER  - 
%0 Journal Article
%A Aravind, N.
%A Narayanan, N.
%A Subramanian, C.
%T Oriented colouring of some graph products
%J Discussiones Mathematicae. Graph Theory
%D 2011
%P 675-686
%V 31
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2011_31_4_a3/
%G en
%F DMGT_2011_31_4_a3
Aravind, N.; Narayanan, N.; Subramanian, C. Oriented colouring of some graph products. Discussiones Mathematicae. Graph Theory, Tome 31 (2011) no. 4, pp. 675-686. http://geodesic.mathdoc.fr/item/DMGT_2011_31_4_a3/

[1] N.R. Aravind and C.R. Subramanian, Forbidden subgraph colorings and the oriented chromatic number, in: 4th International Workshop on Combinatorial Algorithms 4393 (2009) 477-488.

[2] O.V. Borodin, A.V. Kostochka, J. Nesetril, A. Raspaud and É. Sopena, On the maximum average degree and the oriented chromatic number of a graph, Discrete Math. 206 (1999) 77-89, doi: 10.1016/S0012-365X(98)00393-8.

[3] O.V. Borodin, A.V. Kostochka, A. Raspaud and É. Sopena. Acyclic colouring of 1-planar graphs, Discrete Appl. Math. 114 (2001) 29-41, doi: 10.1016/S0166-218X(00)00359-0.

[4] B. Courcelle, The monadic second order logic of graphs. vi. on several representations of graphs by relational structures, Discrete Appl. Math. 54 (1994) 117-149, doi: 10.1016/0166-218X(94)90019-1.

[5] L. Esperet and P. Ochem, Oriented colorings of 2-outerplanar graphs, Information Processing Letters 101 (2007) 215-219, doi: 10.1016/j.ipl.2006.09.007.

[6] G. Fertin, A. Raspaud and A. Roychowdhury, On the oriented chromatic number of grids, Information Processing Letters 85 (2003) 261-266, doi: 10.1016/S0020-0190(02)00405-2.

[7] E. Fried, On homogeneous tournaments, Combinatorial Theory and its Applications 2 (1970) 467-476.

[8] P. Hell and J. Nesetril, Graphs and Homomorphisms, Oxford Lecture Series in Mathematics and its Applications (28), 2004.

[9] T. Herman, I. Pirwani and S. Pemmaraju, Oriented edge colorings and link scheduling in sensor networks, in: SENSORWARE 2006: 1st International Workshop on Software for Sensor Networks, 2006.

[10] W. Imrich and S. Klavžar, Product Graphs : Structure and Recognition (John Wiley Sons, Inc., 2000).

[11] A.V. Kostochka, É. Sopena and X. Zhu, Acyclic and oriented chromatic numbers of graphs, J. Graph Theory 24 (1997) 331-340, doi: 10.1002/(SICI)1097-0118(199704)24:4331::AID-JGT5>3.0.CO;2-P

[12] T.H. Marshall, Homomorphism bounds for oriented planar graphs, J. Graph Theory 55 (2007) 175-190, doi: 10.1002/jgt.20233.

[13] J. Nesetril, A. Raspaud and É. Sopena, Colorings and girth of oriented planar graphs, Discrete Math. 165-166 (1997) 519-530.

[14] P. Ochem, Oriented colorings of triangle-free planar graphs, Information Processing Letters 92 (2004) 71-76, doi: 10.1016/j.ipl.2004.06.012.

[15] A. Pinlou and É. Sopena, Oriented vertex and arc colorings of outerplanar graphs, Information Processing Letters 100 (2006) 97-104, doi: 10.1016/j.ipl.2006.06.012.

[16] A. Raspaud and É. Sopena, Good and semi-strong colorings of oriented planar graphs, Information Processing Letters 51 (1994) 171-174, doi: 10.1016/0020-0190(94)00088-3.

[17] É. Sopena, The chromatic number of oriented graphs, J. Graph Theory 25 (1997) 191-205, doi: 10.1002/(SICI)1097-0118(199707)25:3191::AID-JGT3>3.0.CO;2-G

[18] É. Sopena, Oriented graph coloring, Discrete Math. 229 (2001) 359-369, doi: 10.1016/S0012-365X(00)00216-8.