Geodesic
Oriented Chromatic Number of Cartesian Products $ P_m \square P_n $ and $ C_m \square P_n $
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 3, pp. 799-810.

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

We consider oriented chromatic number of Cartesian products of two paths P_m □ P_n and of Cartesian products of paths and cycles, C_m □ P_n. We say that the oriented graph G is colored by an oriented graph H if there is a homomorphism from G to H. In this paper we show that there exists an oriented tournament H_10 with ten vertices which colors every orientation of P_8 □ P_n and every orientation of C_m □ P_n, for m = 3, 4, 5, 6, 7 and n ≥ 1. We also show that there exists an oriented graph T_16 with sixteen vertices which colors every orientation of C_m □ P_n.
Keywords: graphs, oriented coloring, oriented chromatic number 
@article{DMGT_2022_42_3_a7,
     author = {Nenca, Anna},
     title = {Oriented {Chromatic} {Number} of {Cartesian} {Products} $ P_m \square P_n $ and $ C_m \square P_n $},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {799--810},
     publisher = {mathdoc},
     volume = {42},
     number = {3},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a7/}
}
TY  - JOUR
AU  - Nenca, Anna
TI  - Oriented Chromatic Number of Cartesian Products $ P_m \square P_n $ and $ C_m \square P_n $
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 799
EP  - 810
VL  - 42
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a7/
LA  - en
ID  - DMGT_2022_42_3_a7
ER  - 
%0 Journal Article
%A Nenca, Anna
%T Oriented Chromatic Number of Cartesian Products $ P_m \square P_n $ and $ C_m \square P_n $
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 799-810
%V 42
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a7/
%G en
%F DMGT_2022_42_3_a7
Nenca, Anna. Oriented Chromatic Number of Cartesian Products $ P_m \square P_n $ and $ C_m \square P_n $. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 3, pp. 799-810. http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a7/

[1] H. Bielak, The oriented chromatic number of some grids, Ann. UMCS Inform. AI. 5 (2006) 5–17.

[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. https://doi.org/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. https://doi.org/10.1016/j.ipl.2011.10.019

[4] J. Dybizbański and A. Nenca, Oriented chromatic number of Cartesian products and strong products of paths, Discuss. Math. Graph Theory 39 (2019) 211–223. https://doi.org/10.7151/dmgt.2074

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

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

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

[8] M. Hosseini Dolama and É. Sopena, On the oriented chromatic number of graphs with given excess, Discrete Math. 306 (2006) 1342–1350. https://doi.org/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. https://doi.org/10.1016/j.ipl.2005.03.016

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

[11] A. Pinlou, An oriented coloring of planar graphs with girth at least five, Discrete Math. 309 (2009) 2108–2118. https://doi.org/10.1016/j.disc.2008.04.030

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

[13] T. Rapke, Oriented and injective oriented colourings of grid graphs, J. Combin. Math. Combin. Comput. 89 (2014) 169–196.

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

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

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

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

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

[19] É. Sopena, Upper oriented chromatic number of undirected graphs and oriented colorings of product graphs, Discuss. Math. Graph Theory 32 (2012) 517–583. https://doi.org/10.7151/dmgt.1624

[20] É. Sopena and L. Vignal, A Note on the Oriented Chromatic Number of Graphs with Maximum Degree Three, Research Report, (Bordeaux I University, 1996).

[21] A. Szepietowski, Coloring directed cycles . arXiv:1307.5186

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