SAMS Subject Classification Number: 6

How many non-equivalent \(k\)-colourings of a graph are there? A framework is developed which describes the solution space of this question for three different solution representations: \(k\)-colourings, \(k\)-partitions and partition classes of a graph. The framework exploits relationships between these three solution representations so that information obtained about one representation may be used to obtain information about another. Partition classes are defined and integrated into the existing theory of the framework. An algorithm is developed and implemented to find partitions of odd cycles and another algorithm is developed and implemented to obtain partition classes from those partitions. The partition classes found are used to formulate conjectures which apply to general odd cycles.