Oriented Chromatic Number of Cartesian Products and Strong Products of Paths

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 col- orings 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 with two columns and its orientation which requires 11 colors for oriented coloring. 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 statements were proved with the help of computer programs.

Keywords

• graph
• oriented coloring
• grid
• 05c15