Back to search

University of Victoria (Canada)

2-dipath and proper 2-dipath k-colourings

Abstract

dc:description.abstract

A 2-dipath k-colouring of an oriented graph G is an assignment of k colours, 1,2, . . . , k, to the vertices of G such that vertices joined by a directed path of length two are assigned different colours. The 2-dipath chromatic number is the minimum number of colours needed in such a colouring. There are two possible models, depending on whether adjacent vertices must also be assigned different colours. For both models of 2-dipath colouring we develop the basic theory, including characterizing the oriented graphs that can be 2-dipath coloured using a small number of colours, finding bounds on the 2-dipath chromatic number, determining the complexity of deciding the existence of a 2-dipath k-colouring, describing a homomorphism model, and showing how to determine the 2-dipath chromatic number of tournaments and bipartite tournaments.

Degree

thesis:*
Level thesis:degree_level
Master of Science M.Sc.
Department thesis:degree_department
Department of Mathematics and Statistics
Year dc:date.issued
2011

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Young, Kailyn M.
Advisor dc:contributor.supervisor
  • MacGillivray, Gary

Subjects

dc:subject × 3

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/3277

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

Young, Kailyn M.. 2-dipath and proper 2-dipath k-colourings. Master of Science M.Sc. thesis, 2011. http://hdl.handle.net/1828/3277