Abstract
dc:description.abstractWe define a variation of injective oriented colouring as reflexive injective oriented colouring, or rio-colouring for short, which requires an oriented colouring to be injective on the neighbourhoods of the underlying graph, without requiring the colouring to be proper. An analysis of the complexity of the problem of deciding whether an oriented graph has a k-rio-colouring is considered, and we find a dichotomy for the values of k below 3 and above, being in P or NP-complete, respectively. Characterizations are given for the oriented graphs resulting from the polynomial-time solvable cases, and bounds are given for the rio-chromatic number in terms of maximum in-degree and out-degree, in general, and for oriented trees. Also, a polynomial-time algorithm is developed to aid in the rio-colouring of oriented trees.
Degree
thesis:*- Level thesis:degree_level
- Master of Science M.Sc.
- Department thesis:degree_department
- Department of Mathematics and Statistics
- Year dc:date.issued
- 2009
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Campbell, Russell J.
- Advisors dc:contributor.supervisor
-
- MacGillivray, Gary
- Laca, Marcelo
Subjects
dc:subject × 9Rights
dc:rights- Statement dc:rights
-
- Available to the World Wide Web
- Language dc:language.iso
- en, English
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/1828/2013