A Brief Exploration of Total Colouring

Abstract

A total colouring of a graph is an assignment of colours to the edges and vertices such that adjacent objects receive different colours. In this thesis, we prove partial results towards the Total Colouring Conjecture which states that the total chromatic number of a graph is at most degree plus two. In the first part of this thesis there is an almost complete categorization of which total graphs are perfect. Upper bounds on the total chromatic number are found for Cartesian, strong, and tensor graph products. We determine that the total chromatic number of the Cartesian graph product depends strongly on the total chromatic number of the component graphs. Lastly, we explore how vertex multiplication affects the total chromatic number. We establish that for the star graph and cycle graph, no matter how many times a vertex is multiplied, the resulting graph satisfies the Total Colouring Conjecture.