Oriented chromatic number of Cartesian products and strong products of paths

Janusz Dybizbański , Anna Nenca


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 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.
Author Janusz Dybizbański (FMPI / II)
Janusz Dybizbański,,
- Institute of Informatics
, Anna Nenca (FMPI / II)
Anna Nenca,,
- Institute of Informatics
Journal seriesDiscussiones Mathematicae Graph Theory, ISSN 1234-3099, (N/A 70 pkt)
Issue year2019
Publication size in sheets0.6
Keywords in Englishgraph, oriented coloring, grid
ASJC Classification2604 Applied Mathematics; 2607 Discrete Mathematics and Combinatorics
URL http://www.discuss.wmie.uz.zgora.pl/php/discuss3.php?ip=&url=pdf&nIdA=25578&nIdSesji=-1
Languageen angielski
LicenseJournal (articles only); published final; Other open licence; with publication
Score (nominal)70
Score sourcejournalList
ScoreMinisterial score = 70.0, 28-01-2020, ArticleFromJournal
Publication indicators WoS Citations = 0; Scopus SNIP (Source Normalised Impact per Paper): 2018 = 0.934; WoS Impact Factor: 2018 = 0.741 (2) - 2018=0.611 (5)
Citation count*1 (2020-04-05)
Share Share

Get link to the record

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Are you sure?