Show simple item record

dc.contributor.authorMacKeigan, Kyle
dc.date.accessioned2021-09-01T16:30:24Z
dc.date.available2021-09-01T16:30:24Z
dc.date.issued2021-09-01T16:30:24Z
dc.identifier.urihttp://hdl.handle.net/10222/80796
dc.description.abstractTwo colourings of a graph are orthogonal if when two elements are coloured with the same colour in one of the colourings, then those elements receive distinct colours in the other colouring. First, we study the orthogonal chromatic number of Cayley graphs and bipartite graphs. In particular, we determine which cycle graphs, Paley graphs, circulant graphs, and tree graphs have an optimal orthogonal colouring. Orthogonal colourings of graphs that are constructed by graph products are then explored. We show that if one component has an optimal orthogonal colouring, then the resulting Cartesian, tensor, and strong product graph has an optimal orthogonal colouring under certain conditions. In addition, we determine which hypercube graphs and Hamming graphs have an optimal orthogonal colouring. Next, orthogonal colourings of graphs that are randomly generated are considered. In particular, we study the random geometric model and the Erdos-Renyi model. We show which random geometric graphs have an optimal orthogonal colouring with high probability. Additionally, we obtain an upper bound on the orthogonal chromatic number in terms of the chromatic number with high probability for both models. Lastly, a variation of orthogonal colourings, called (k,t)-orthogonal colourings, is discussed. We establish a categorization of graphs having an optimal (k,t)-orthogonal colouring. Next, we generalize the results for orthogonal colourings of graph products to (k,t)-orthogonal colourings of graph products. Also, we show which cycle graphs have an optimal (2,t)-orthogonal colouring.en_US
dc.language.isoenen_US
dc.subjectGraph Colouringen_US
dc.subjectOrthogonal Colouringen_US
dc.subjectGraph Producten_US
dc.subjectRandom Graphen_US
dc.titleAn Exploration of Orthogonal Colouringsen_US
dc.date.defence2021-08-18
dc.contributor.departmentDepartment of Mathematics & Statistics - Math Divisionen_US
dc.contributor.degreeDoctor of Philosophyen_US
dc.contributor.external-examinerDanny Dyeren_US
dc.contributor.graduate-coordinatorSara Faridien_US
dc.contributor.thesis-readerJason Brownen_US
dc.contributor.thesis-readerRichard Nowakowskien_US
dc.contributor.thesis-supervisorJeannette Janssenen_US
dc.contributor.ethics-approvalNot Applicableen_US
dc.contributor.manuscriptsNot Applicableen_US
dc.contributor.copyright-releaseNot Applicableen_US
 Find Full text

Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record