Geodesic
Oriented Chromatic Number of Cartesian Products and Strong Products of Paths
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 1, pp. 211-223.

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

An oriented coloring of an oriented graph G is a homomorphism from G to H such that H is without selfloops and arcs in opposite directions. We shall say that H is a coloring graph. In this paper, we focus on oriented col- orings of Cartesian products of two paths, called grids, and strong products of two paths, called strong-grids. We show that there exists a coloring graph with nine vertices that can be used to color every orientation of grids with five columns. We also show that there exists a strong-grid with two columns and its orientation which requires 11 colors for oriented coloring. Moreover, we show that every orientation of every strong-grid with three columns can be colored by 19 colors and that every orientation of every strong-grid with four columns can be colored by 43 colors. The above statements were proved with the help of computer programs.
Keywords: graph, oriented coloring, grid 
@article{DMGT_2019_39_1_a16,
     author = {Dybizba\'nski, Janusz and Nenca, Anna},
     title = {Oriented {Chromatic} {Number} of {Cartesian} {Products} and {Strong} {Products} of {Paths}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {211--223},
     publisher = {mathdoc},
     volume = {39},
     number = {1},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a16/}
}
TY  - JOUR
AU  - Dybizbański, Janusz
AU  - Nenca, Anna
TI  - Oriented Chromatic Number of Cartesian Products and Strong Products of Paths
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2019
SP  - 211
EP  - 223
VL  - 39
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a16/
LA  - en
ID  - DMGT_2019_39_1_a16
ER  - 
%0 Journal Article
%A Dybizbański, Janusz
%A Nenca, Anna
%T Oriented Chromatic Number of Cartesian Products and Strong Products of Paths
%J Discussiones Mathematicae. Graph Theory
%D 2019
%P 211-223
%V 39
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a16/
%G en
%F DMGT_2019_39_1_a16
Dybizbański, Janusz; Nenca, Anna. Oriented Chromatic Number of Cartesian Products and Strong Products of Paths. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 1, pp. 211-223. http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a16/

[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] O.V. Borodin, A.V. Kostochka, J. Nešetřil, 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] J. Dybizbański and A. Nenca, Oriented chromatic number of grids is greater than 7, Inform. Process. Lett. 112 (2012) 113-117. doi: 10.1016/j.ipl.2011.10.019

[4] J. Dybizbański and A. Szepietowski, The oriented chromatic number of Halin graphs, Inform. Process. Lett. 114 (2014) 45-49. doi: 10.1016/j.ipl.2013.09.011

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

[6] E. Fried, On homogeneous tournaments, Combin. Theory Appl. 2 (1970) 467-476.

[7] 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:4h331::AID-JGT5i3.0.CO;2-P

[8] M. Hosseini Dolama and É. Sopena, On the oriented chromatic number of graphs with given excess, Discrete Math. 306 (2006) 1342-1350. doi: 10.1016/j.disc.2005.12.023

[9] M. Hosseini Dolama and É. Sopena, On the oriented chromatic number of Halin graphs, Inform. Process. Lett. 98 (2006) 247-252. doi: 10.1016/j.ipl.2005.03.016

[10] B.D. McKay and A. Piperno, Practical graph isomorphism, II, J. Symbolic Comput. 60 (2013) 94-112. doi: 10.1016/j.jsc.2013.09.003

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

[12] É. Sopena, Homomorphisms and colourings of oriented graphs: An updated survey, Discrete Math. 339 (2016) 1993-2005. doi: 10.1016/j.disc.2015.03.018

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

[14] É. Sopena, The chromatic number of oriented graphs, J. Graph Theory 25 (1997) 191-205. doi: 10.1002/(SICI)1097-0118(199707)25:3h191::AID-JGT3i3.0.CO;2-G

[15] É. Sopena, There exist oriented planar graphs with oriented chromatic number at least sixteen, Inform. Process. Lett. 81 (2002) 309-312. doi: 10.1016/S0020-0190(01)00246-0

[16] É. Sopena, Upper oriented chromatic number of undirected graphs and oriented col- orings of product graphs, Discuss. Math. Graph Theory 32 (2012) 517-533. doi: 10.7151/dmgt.1624

[17] É. Sopena and L. Vignal, A note on the oriented chromatic number of graphs with maximum degree three, Research Report (Bordeaux I University, 1996).

[18] A. Szepietowski and M. Targan, A note on the oriented chromatic number of grids, Inform. Process. Lett. 92 (2004) 65-70. doi: 10.1016/j.ipl.2004.06.014.