The oriented chromatic number of some grids

Halina Bielak

Abstract


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.

Full Text:

PDF


DOI: http://dx.doi.org/10.17951/ai.2006.5.1.5-17
Date of publication: 2006-01-01 00:00:00
Date of submission: 2016-04-27 10:15:45


Statistics


Total abstract view - 244
Downloads (from 2020-06-17) - PDF - 0

Indicators



Refbacks

  • There are currently no refbacks.


Copyright (c) 2015 Annales UMCS Sectio AI Informatica

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.