An Exploration of Orthogonal Colourings

Abstract

Two 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.