Oriented chromatic number of Cartesian products and strong products of paths

Janusz Dybizbański , Anna Nenca

Abstract

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, (A 15 pkt)
Issue year2019
Vol39
No1
Pages211-223
Publication size in sheets0.6
Keywords in Englishgraph, oriented coloring, grid
DOIDOI:10.7151/dmgt.2074
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)15
ScoreMinisterial score = 15.0, 06-11-2018, ArticleFromJournal
Ministerial score (2013-2016) = 15.0, 06-11-2018, ArticleFromJournal
Publication indicators WoS Impact Factor: 2016 = 0.302 (2)
Citation count*
Cite
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.
Back