Topics in graph colouring and extremal graph theory

Abstract

In this thesis we consider three problems related to colourings of graphs and one problem in extremal graph theory. Let be a connected graph with vertices and maximum degree . Let denote the graph with vertex set all proper -colourings of and two -colourings are joined by an edge if they differ on the colour of exactly one vertex.
Our first main result states that has a unique non-trivial component with diameter . This result can be viewed as a reconfigurations analogue of Brooks' Theorem and completes the study of reconfigurations of colourings of graphs with bounded maximum degree.
A Kempe change is the operation of swapping some colours , of a component of the subgraph induced by vertices with colour or . Two colourings are Kempe equivalent if one can be obtained from the other by a sequence of Kempe changes. Our second main result states that all -colourings of a graph are Kempe equivalent unless is the complete graph or the triangular prism. This settles a conjecture of Mohar (2007).
Motivated by finding an algorithmic version of a structure theorem for bull-free graphs due to Chudnovsky (2012), we consider the computational complexity of deciding if the vertices of a graph can be partitioned into two parts such that one part is triangle-free and the other part is a collection of complete graphs. We show that this problem is NP-complete when restricted to five classes of graphs (including bull-free graphs) while polynomial-time solvable for the class of cographs.
Finally we consider a graph-theoretic version formulated by Holroyd, Spencer and Talbot (2007) of the famous Erds-Ko-Rado Theorem in extremal combinatorics and obtain some results for the class of trees.