The labelling of graphs through colouring

Abstract

Graph theory is a well-known area in the research field of mathematics. Its evolution started off with the quest of solving questions or games involving numbers. This led to the colouring of graphs; a way of labelling graph vertices or edges while having some constraints. In this dissertation, four chapters are presented. The first three, which constitute the major part of the thesis, are related to vertex graph colouring. The final one is a very short section on edge colouring. By researching vertex colouring, a number of key results were identified. A particular and important one is Brooks’ Theorem. This result can be proved to be true by making use of different techniques. In this study six of these methods are taken into account and presented in the second chapter as follows: a) A Greedy Colouring of G, b) A Partitioning Approach, c) Kempe Chains, d) Reducing to the cubic case, e) Kernel Perfection, and f) The Degree Choosable Graph. A well known subsection of vertex colouring and which has been recently regarded as an area of interest is list colouring and choosability. The famous result by Thomassen about the choosability of planar graphs is discussed, whilst mentioning other key results related to list colouring and choosability. The final chapter of this research is about Vizing’s Theorem, Vizing’s Theorem for multigraphs and Vizing’s Theorem for a precolouring extension of G.