FEGHALI, CARL (2016) *Topics in graph colouring and extremal graph theory.* Doctoral thesis, Durham University.

| PDF - Accepted Version 784Kb |

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

Item Type: | Thesis (Doctoral) |
---|---|

Award: | Doctor of Philosophy |

Keywords: | graph colouring; graph partitioning; extremal graph theory |

Faculty and Department: | Faculty of Science > Engineering and Computing Science, School of |

Thesis Date: | 2016 |

Copyright: | Copyright of this thesis is held by the author |

Deposited On: | 14 Oct 2016 10:50 |