Back to search

University of Victoria (Canada)

Reflexive injective oriented colourings

Abstract

dc:description.abstract

We 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 × 9

Rights

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

Chain of custody

source
Harvested from
University of Victoria (Canada)
Base URL
dspace.library.uvic.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Campbell, Russell J.. Reflexive injective oriented colourings. Master of Science M.Sc. thesis, 2009. http://hdl.handle.net/1828/2013