Grundy oriented colouring
LE3 .A278 2013
2013
Clarke, Nancy
Acadia University
Bachelor of Science
Honours
Mathematics and Statistics
Mathematics & Statistics
To properly colour the vertices of a simple graph, one can use the Greedy colouring algorithm which assigns to vertex v of a graph G the least indexed colour not already used on the neighbours of v. The maximum number of colours used in any applica- tion of the Greedy colouring algorithm is called the Grundy number of G. Grundy colouring is well-studied for undirected graphs and will be de ned here for oriented graphs. Three possible de nitions for Grundy oriented colouring will be explored. Bounds will be given for the Grundy number on common classes of oriented graphs including paths, cycles, trees and graph products for the de nitions considered. The lexico- graphic product will be investigated in further detail. The idea of oriented cliques and oriented Grundy cliques will be explored. Results for the Grundy number of oriented and unoriented graphs will be compared as well as comparisons between the two possible de nitions will be investigated.
The author retains copyright in this thesis. Any substantial copying or any other actions that exceed fair dealing or other exceptions in the Copyright Act require the permission of the author.
https://scholar.acadiau.ca/islandora/object/theses:975