The oriented chromatic number of some grids.
Halina Bielak · Studia Iuridica Lublinensia (Uniwersytet Marii Curie-Skłodowskiej w Lublinie) · 2006
We define some infinite subfamily of hexagonal grids with the oriented chromatic number 5. We present an algorithm for oriented colouring of some hexagonal planar oriented grids. The algorithm uses BFS spanning tree of a subgraph of the dual graph of the grid and a homomorphism to some tournament of order 6. In general the difference between the number of colours given by the algorithm and the oriented chromatic number is at most 1.