Geodesic
Upper oriented chromatic number of undirected graphs and oriented colorings of product graphs
Discussiones Mathematicae. Graph Theory, Tome 32 (2012) no. 3, pp. 517-533

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

The oriented chromatic number of an oriented graph ^→G is the minimum order of an oriented graph ^→H such that ^→G admits a homomorphism to ^→H. The oriented chromatic number of an undirected graph G is then the greatest oriented chromatic number of its orientations.
Keywords: product graph, oriented coloring, oriented chromatic number 
Sopena, Éric. Upper oriented chromatic number of undirected graphs and oriented colorings of product graphs. Discussiones Mathematicae. Graph Theory, Tome 32 (2012) no. 3, pp. 517-533. http://geodesic.mathdoc.fr/item/DMGT_2012_32_3_a10/
@article{DMGT_2012_32_3_a10,
     author = {Sopena, \'Eric},
     title = {Upper oriented chromatic number of undirected graphs and oriented colorings of product graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {517--533},
     year = {2012},
     volume = {32},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2012_32_3_a10/}
}
TY  - JOUR
AU  - Sopena, Éric
TI  - Upper oriented chromatic number of undirected graphs and oriented colorings of product graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2012
SP  - 517
EP  - 533
VL  - 32
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DMGT_2012_32_3_a10/
LA  - en
ID  - DMGT_2012_32_3_a10
ER  - 
%0 Journal Article
%A Sopena, Éric
%T Upper oriented chromatic number of undirected graphs and oriented colorings of product graphs
%J Discussiones Mathematicae. Graph Theory
%D 2012
%P 517-533
%V 32
%N 3
%U http://geodesic.mathdoc.fr/item/DMGT_2012_32_3_a10/
%G en
%F DMGT_2012_32_3_a10

[1] N.R. Aravind, N. Narayanan and C.R. Subramanian. Oriented colouring of some graph products, Discuss. Math. Graph Theory 31 (2011) 675-686, doi: 10.7151/dmgt.1572.

[2] N.R. Aravind and C.R. Subramanian. Forbidden subgraph colorings and the oriented chromatic number, in: Proc. 20th Int. Workshop on Combinatorial Algorithms, IWOCA'09, Lecture Notes in Comput. Sci. 5874 (2009) 60-71, doi: 10.1007/978-3-642-10217-2_9.

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

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

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

[6] 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

[7] J.W. Moon, Topics on Tournaments (Holt, Rinehart and Winston, New York, 1968).

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

[9] P. Ochem. Negative results on acyclic improper colorings, Proc. Euro Comb'05, Discrete Math. Theoret. Comput. Sci., Conference Volume AE (2005) 357-362.

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

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

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

[13] É. Sopena and L. Vignal, A note on the oriented chromatic number of graphs with maximum degree three, Research Report (1996), http://www.labri.fr/perso/sopena/.

[14] D.R. Wood, On the oriented chromatic number of dense graphs, Contributions to Discrete Math. 2 (2007) 145-152.