Oriented and Injective Oriented Colourings of Grid Graphs

An oriented coloring of a directed graph is a vertex coloring in which no two adjacent vertices belong to the same color class and all of the arcs between any two color classes have the same direction. Injective oriented colorings are oriented colorings that satisfy the extra condition that no two in-neighbors of a vertex receive the same color. The oriented chromatic number of an unoriented graph is the maximum oriented chromatic number over all possible orientations. Similarly, the injective oriented chromatic number of an unoriented graph is the maximum injective oriented chromatic number over all possible orientations. The main results obtained in this paper are bounds on the injective oriented chromatic number of two-dimensional grid graphs.