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, (A 15 pkt)|
|Publication size in sheets||0.6|
|Keywords in English||graph, oriented coloring, grid|
|License||Journal (articles only); published final; ; with publication|
|Score||= 15.0, 24-07-2019, ArticleFromJournal|
|Publication indicators||= 0; : 2016 = 0.659; : 2017 = 0.601 (2) - 2017=0.535 (5)|
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.