Return to search

2-dipath and proper 2-dipath k-colourings / Two-dipath and proper two-dipath k-colourings

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. / Graduate

Identiferoai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/3277
Date02 May 2011
CreatorsYoung, Kailyn M.
ContributorsMacGillivray, Gary
Source SetsUniversity of Victoria
LanguageEnglish, English
Detected LanguageEnglish
TypeThesis
RightsAvailable to the World Wide Web

Page generated in 0.0015 seconds