The oriented chromatic number of some grids
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:
PDFDOI: 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 - 385
Downloads (from 2020-06-17) - PDF - 0
Indicators
Refbacks
- There are currently no refbacks.
Copyright (c) 2015 Annales UMCS Sectio AI Informatica
This work is licensed under a Creative Commons Attribution 4.0 International License.