DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2023): 0.5

5-year Journal Impact Factor (2023): 0.6

CiteScore (2023): 2.2

SNIP (2023): 0.681

Discussiones Mathematicae Graph Theory

Article in volume

Authors:

A. Nenca

Anna Nenca

University of Gdańsk

email: anenca@inf.ug.edu.pl

Title:

Oriented chromatic number for Cartesian products $P_m\Box P_n$ and $C_m\Box P_n$

PDF

Source:

Discussiones Mathematicae Graph Theory 42(3) (2022) 799-810

Received: 2019-06-05 , Revised: 2020-01-31 , Accepted: 2020-02-03 , Available online: 2020-02-24 , https://doi.org/10.7151/dmgt.2307

Abstract:

\( \newcommand{\ora}{\overrightarrow} \)We consider oriented chromatic number of Cartesian products of two paths $P_m\Box P_n$ and of Cartesian products of paths and cycles, $C_m\Box P_n$. We say that the oriented graph $\overrightarrow G$ is colored by an oriented graph $\ora H$ if there is a homomorphism from $\ora G$ to $\overrightarrow H$. In this paper we show that there exists an oriented tournament $\overrightarrow H_{10}$ with ten vertices which colors every orientation of $P_8 \Box P_n$ and every orientation of $C_m \Box P_n$, for $m=3,4,5,6,7$ and $n\geq 1$. We also show that there exists an oriented graph $\overrightarrow T_{16}$ with sixteen vertices which colors every orientation of $C_m \Box P_n$.

Keywords:

graphs, oriented coloring, oriented chromatic number

References:

  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,, 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
Close