Oriented chromatic number of Cartesian products and strong products of paths
Janusz Dybizbański , Anna Nenca
AbstractAn 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 colorings 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 wit h two columns and its orientation which requires 11 colors for oriented co loring. 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 statement s were proved with the help of computer programs.
|Journal series||Discussiones Mathematicae Graph Theory, ISSN 1234-3099, (N/A 70 pkt)|
|Publication size in sheets||0.6|
|Keywords in English||graph, oriented coloring, grid|
|License||Journal (articles only); published final; ; with publication|
|Score||= 70.0, 28-01-2020, ArticleFromJournal|
|Publication indicators||= 0; : 2018 = 0.934; : 2018 = 0.741 (2) - 2018=0.611 (5)|
|Citation count*||1 (2020-04-05)|
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.